Vlad the Impaler (otherwise known as Vlad Dracula) achieved this reputation with the Ottoman Turks. According to records of the day, he once stopped a Turkish army that greatly outnumbered his by ambushing its vanguard (away from the rest of the force) and mounting them all on spikes—not their heads, the entire person, usually still alive and screaming. The rest of the Turkish army was so appalled at the sight that it decided it didn't want to fight anymore. The man was so dreaded that upon Vlad's death, the Ottomans had his head hung from the walls of Constantinople to help convince people he was gone for good. Not surprisingly, Christian Wallachians were fond of him, not just for his martial successes but for his various social and economic reforms.
Referenced by the Heralds in Assassin's Creed: Revelations: "To all visitors seeking the head of Voivode Dracula: Yes, we have it. Yes, he's dead. No, you cannot see it. No, he will not come invade you again. It has been over thirty years, now please stop asking!"
There's a (probably apocryphal) story that a cart laden with treasure and gold was left overnight in the middle of a street in Vlad's territory, and was left completely untouched, so much did his subjects fear him.
Genghis Khan used this as his modus operandi. If you didn't submit the moment the Mongols demanded it, you were butchered. Simple as that. Genghis's subordinates were even worse than him in this regard; Genghis at least practiced a degree of brutal pragmatism in his campaigns in China. In the regions conquered by his generals, entire countries were left utterly devastated. On his death bed he told everyone to make sure the enemies in the next battle didn't know about his demise, so he could scare the crap out of people even when he was dead.
Pirates of the Atlantic in the 17th and 18th centuries. If you hove to and handed over the supplies and sailors they wanted (they ruthlessly took carpenters, coopers, and smiths especially) then they'd let you sail off. If you tried to run away or dumped valuables overboard... God have mercy, because the pirates wouldn't.
Josef Stalin made a science of this trope. After he took control of the Communist Party, the show trials he arranged to execute his political opponents filled his cronies with such dread that they were terrified of invoking the wrath of the Vozhd ("Führer" in German or "leader" in English) and would never dare try to depose him. Rumors abound that Stalin eventually died from being poisoned, which is pretty much the only way anyone could have stood against him. There is also some evidence that his servants heard him dying but didn't summon any doctors for fear of what would happen to them if they were mistaken.
The nickname of Ivan the Terrible is actually this trope, "terrible" being a mistranslation. He was indeed feared by his subjects, primarily not because of his total death toll - his reign coincided with the golden age of Inquisition and the struggle between Catholics and Protestants in Europe, so he was a rather moderately brutal king by his century's standards. But he had an unpredictable personality, was prone to onslaughts of rage and liked the more alternative methods of capital punishment.
Saddam Hussein's closest advisors were so terrified of displeasing him that they told him he could beat the US armed forces. In 2003. He couldn't. He was so amazingly feared that during his trial, when he wandered in all disheveled and malnutritioned, the jury still reeled in horror. It's actually a testament to their courage they managed to find him guilty, so frightened were they of reprisals and reputation both. Even after being found guilty Saddam felt he still had full control of his country and DEMANDED he be presented with a firing squad like a true soldier, but as we know, he didn't quite get his final wish.
All South American and Latin American dictators are this. Fulgencio Bastista and Fidel Castro in Cuba, Augusto Pinochet In Chile, Jorge Videla in Argentina, Anastasio Somoza in Nicaragua and Leonidas Trujillo in the Dominican Republic.
Porfirio Diaz in Mexico played with this trope: While he was (and still is) hated in his time due of his iron-hand policies, he hardly was the most feared dictator Mexico had, only the most notorious one since he ruled for about 35 years. On the other hand, Victoriano Huerta (who succeded Diaz after executing Francisco I. Madero) was (and still is) the most hated dictator Mexico ever had, despise he only ruled for only one year, but the atrocities he did during his rule managed to outshine anything that Diaz did during his three-decade rule, to the grade there's an award in Mexico named the Belisario Domínguez Medal of Honor after the aforementioned man who opposed him, and Huerta's men killed him, not before cutting his tongue out from his corpse.
Basically every notable warrior (and a couple government officials too) got at least one mention of them being regarded as this by one of the other sides in the Three Kingdoms era of Chinese history, but Zhang Liao got to truly live up to this trope as he was able to rout a force of 100,000 with only 800 men, and was said to be so feared crying children would grow silent in his wake.
Its hard to imagine the Mike Tyson we know now-a-days to be the dreaded, but in his prime he was considered unbeatable and he truly terrified his opponents. It also helped that he played up his reputation by walking into the ring without music and unrelentingly staring down his opponent, psychologically unnerving them. Oh yeah, he hitbloody hard too◊
Many successful military commanders have been this to their opponents. Napoleon terrified his enemies, as did Lord Horatio Nelson, to give two examples from the Napoleonic Wars.
Napoleon and Hannibal (from the Second Punic War) stand out as two of the only military commanders in history whose enemies have paid them the ultimate compliment of redesigning entire strategies specifically to avoid facing them personally in battle.
The Wehrmacht was this in the early stages of World War II. Indeed, after Operation Barbarossa bogged down in sight of Moscow, General Franz Halder invoked this trope. "The myth of our invincibility is shattered."
Not to mention the SS and earlier the SA. Also the Russian Army that finally made it into ransacked Germany.
The Japanese Army would also count, across Asia people would run and hide when Japanese troops were approaching, as they were afraid of not being killed, but by being sent into the horrendous prison camps.
Edward Teach aka "Blackbeard", the most infamous pirate in the world. Anyone who saw his ship, the Queen Anne's Revenge, would surrender immediately rather than put up a fight with him. He intentionally cultivated this sort of fear by, among other things, tying burning scraps of paper into his beard o give the impression that he was on fire in battle.
The Royal Navy was this to the Italian Navy in World War II: while the Italian high officers thought they could win and control the Mediterranean, the sailors and the officers who actually sailed against the Brits (plus a few of the members of the high command) openly admitted they were doomed and their success would be measured by the length of their resistance and the losses they'd inflict before the ultimate defeat. Interestingly, the special operation branch of the Italian Navy had the same reputation among the Royal Navy, especially after that time they sank two battleship in Alexandria's harbor, one of which had the commanding admiral on board (the battleships were recovered and repaired, but remained disabled for months and the Royal Navy didn't dare to lower its guard for the rest of the war).
The Italian Navy (Regia Marina) was built with French Navy as the assumed enemy and to counter the French threat. Their cruisers and battleships were optimized to fight their French opponents. The Italian admirals never even thought having to face the Royal Navy. When they did, they were somewhat demoralized.
And it was that also to the Kriegsmarine. Grand Admiral Erich Raeder openly admitted to Hitler that his forces were so underpowered that all he could do was to fight bravely before the ultimate defeat. After the Operation Weserübung, which cost the Kriegsmarine two cruisers, one battlecruiser seriously damaged and dozens of destroyers, the Kriegsmarine was especially ordered to avoid the White Ensign and concentrate on the Red - the British merchantmen.
The Gurkhas. The Pashtun of eastern Afghanistan and Pakistan believe that the Gurkhas are immortal demons, who eat the bodies of the men they kill. Such is their reputation, it's said that during The Falklands War, a British captain casually radioed over to an attacking Argentinian vessel, informing them they had a company of Gurkhas onboard. Cue the Argentinian vessel immediately retreating.
The regular British military has a somewhat similar reputation for their bayonet charges. In the same war, just hearing a British officer shout "FIX BAYONETS!" would sometimes result in the enemy disengaging or even surrendering immediately.
Swiss mercenaries were considered the best soldiers in the world for several hundred years. To make sure everyone on the battlefield knew exactly who they were, they took to wearing outrageously colorful uniforms. The uniforms of the Vatican's Swiss Guard is a relic of this custom.
They were so feared that a treaty ending a war between several major powers specifically stated that no one was allowed to hire Swiss mercenaries. Ever.
Simo Häyhä, the legendary Finnish sniper who earned the most recorded sniper kills (505) in any major war, repeatedly wiped out mortar units and enemy snipers sent specifically to eliminate him and most impressively of all, only had iron sights to aim with. This eventually earned him the nickname of "The White Death".
Whilst being shot in the face, he simultaneously managed to take out the sniper that shot him, before lapsing into a coma. He awoke on the same day the Russians called a ceasefire, leading some to joke that the Red Army did so because they were too afraid of facing him again.
So feared of him were the Russians, they basically said "FUCK EVERYTHING, JUST NUKE THE BASTARD!" So they dropped an artillery strike on where he was thought to be. It didn't kill him.
Theodore Roosevelt. It was said that he died in his sleep because Death was too afraid to take him awake.
Honey badgers. They're famous for being avoided by every predator in Africa, and have been known to chase away elephants and eat (young) jackals and crocodiles.
Wolverines too. They've been known to chase away bears and cougars from their kills.
Golden eagles have been spotted chasing grizzly bears and scaring badgers not dissimilar to honey badgers away from a meal.
Notorious gangster Al Capone was terrifying both to the police and to rival gangs.
Diseases can be pretty terrifying in this way too, such as cancer or AIDS.
In the 1980s, AIDS was a mysterious disease no one knew about, except that it was fatal. Over time as more effective treatments and preventatives came out, it lost much of its dreaded title, though since there's no cure, it's still pretty dreaded.
Cancer comes along in so many different forms, each one more or less deadly than the others. While some cancers like squamous-cell carcinoma aren't very deadly, others like pancreatic cancer and lung cancer have much higher death rates and are considered much more threatening and scary.
AIDS and cancer are so dreaded that thinking you had it but being tested negative are known as AIDS scares or cancer scares.
In a humorous American Football example, Bernard Pollard is this to New England Patriot fans. He's caused no less than 4 injuries to Patriot players over the past few seasons, all of which completely altered the Patriots' seasons for the worse.
Fans will have their heart skip a beat if a star player on their team gets injured and they hear that the player has scheduled an appointment to see Dr. James Andrews. Dr. Andrews is obviously not a bad guy - he is very highly regarded and is considered one of the best specialists in knee, elbow, and shoulder surgery (three things which get hurt a lot in sports) - but if the player's going to see Dr. Andrews, it means the injury is bad (season-ending surgery is not infrequent).