Mr. Croup and Mr. Vandemar, the Old Firm, from Neil Gaiman's Neverwhere. "Obstacles obliterated, nuisances eradicated, bothersome limbs removed, and tutelary dentistry." Interestingly it lampshades the Brains and Brawn nature of the pair by referring to them as "the fox and the wolf" at several points. One theory on that point is that they're actually different werewolves.
The demons (Dukes of Hell) Hastur and Ligur in Good Omens also fit pretty well.
Mr. Pin and Mr. Tulip, the New Firm, from The Truth are based on the archtype, and contain references to other Those Two Bad Guys pairs, like Jules and Vincent. "Do you know what they call sausage-in-a-bun in Quirm?"
In The Art of Discworld, Pratchett lays out the principle of this trope — if a gang has two members (a "gangette"), one will do the thinking and the other will "talk like dis". If there is a third, the same applies but the third guy will be called Fingers.
Robert Asprin's Myth Adventures series has Guido and Nunzio, who work for the main character Skeeve as part of his new connection to the Mafia. It ends up neither one is that bad, and Guido has a history in the theater. And a degree in business administration. Also, Nunzio worked as an elementary school (primary school, for our royal cousins) teacher in the past. Also, oddly, as an animal trainer.
Hawker and Boon, the schoolboy-suited Prefects from Jonathan Barnes' The Somnambulist. They are called into service by a greyish protagonist, but they really are not nice people.
Pex and Chips from Artemis Fowl: The Eternity Code, though they are conspicuously lacking on the Brains side.
Mr. Skruff and Mr. Valdemar from the Norwegian-only children's book Kampen om Speilet (The Battle for the Mirror) fits this trope to a T, up to and including tall-and-thin/short-and-plump builds and eloquent speech. Chief lackeys to Evil Sorcerer Vesperon, they are notable for obsessing over finding the right answers for the right questions and cheerfully killing forest animals by blowing cherry stones at them.
Bookend killers, bonebreakers, and all round intimidators Crask and Sadler from Glen Cook's Garrett, P.I. stories fit this trope like a kidskin glove. After all, they do give people a sporting chance... if you can make it from the middle of the lake to the shore faster than them, they'll let you go, no hard feelings. Did they forget to mention the 100 pounds tied to your legs? Oops...
Sean Cullen's Hamish X series has Mr. Sweet and Mr. Candy.
Mr. Wint and Mr. Kidd from Ian Fleming's Diamonds Are Forever (1956), probably the Ur Example of this trope... except unlike most examples, they're explicitly a couple. Romantically. They bang.
Blue and Grey, who menace protagonist Joe Sixsmith in Reginald Hill's novel Blood Sympathy. Blue has pretensions to intelligence and is Faux Affably Evil; Grey is openly uncouth. Both are dangerous men.
Rosencrass and Guildenswine (their names being one of many shout-outs to William Shakespeare). Usually they're just spies, but near the end of Castle Storm they commit murder on a whim and are willing to kill Sylver and his gang for money. Since they do this in a magical forest, this proves to be their downfall.
Both depicted generations of the Herk and Bare families could also fall into this category — the first pair are mercenaries, and the second pair are graverobbers.
Two of Eva Ibbotson's young adult novels — The Dragonfly Pool and Journey to the River Sea — have comically villainous duos who are hired to kidnap the hero.
Haruki Murakami's Hard-Boiled Wonderland and the End of the World features "Big Boy" and "Junior", who try to extort information about the Professor's dealings from the book's protagonist midway through the book.
Mr and Mrs Cavendish in the Nightside book Nightingale's Lament. They run a nightclub where the singer Rossignol, the titular Nightingale, performs, but because they put her through a process which left her mostly dead, her voice now induces her listeners to commit suicide.
Simon R. Green also plays with this one a bit in one of his Secret Histories books: first he invokes it straight with the Russian werewolf/gangsters, the Vodyanoi brothers, and then he parodies it with a couple of Mooks who get so caught up bickering with one another that they forget they're supposed to be intimidating the hero.
Tom and Ty in Simon Spurrier's Contract, two thugs acting as disposable backup for Michael Point, a professional assassin. Tom's a frustrated New Zealander with a taste for casual ultraviolence and Speed, and Ty's a hulking Jamaican who never speaks louder than a whisper. They're also short-livedScrappies.
The Duke and the Dauphin from the Adventures of Huckleberry Finn are Con Artists, not killers, but they're still the lead antagonists who do the heroes the most harm. However, they are not a villainous duo prior to their introduction in the novel, but become one shortly after meeting up.
Finney and Mudd, Felix Jongleur's hirelings in Tad Williams' doorstopper quadrilogy Otherland — not only do they oppress and sometimes torture his employees, but AIs inspired by them wreak havoc in the titular computer network, taking on various forms including creepy versions of the Walrus and the Carpenter.
In Warbreaker, Denth and Tonk Fah may qualify, though Denth is such an Affably EvilMagnificent Bastard that we don't know that they're bad guys for about half the book.
Gotz And Meyer makes Those Two Bad Guys the focus of the story, as a teacher several decades later reads of their part in the Holocaust and tries to figure out what their motivations were. We don't quite figure it out — the research drives him insane.
Agents Myers & Franks from Monster Hunter International. Myers is the polite, educated one, and Franks is the quiet, brutal one who's quite capable of curb-stomping the hero, Owen Pitt. (Owen managed to kill a rampaging werewolf with his bare hands in the opening chapter, so that should tell you just what a badass Franks is...) Both are full-blown Knights Templar.
Bauchelain & Korbal Broach from Steven Erikson's Malazan books. One's an intelligent scholarly (and completely immoral) summoner/conjurer, the other's a necromancer, nearly always silent and a eunuch to boot. What a lovely pair of monsters they are.
Practicals Severard and Frost from The First Law, the personal assistants of Inquisitor Glokta. They're like secretaries. Scary, twisted secretaries.
In his days working for the Mafia-like Jhereg, Vlad Taltos had a pair of thugs working for him called Sticks and Shoen ("Sticks and Stone(s)"). Shoen is short for his species and more of a brute, whereas Sticks is very tall and is personable off the job.
SyFy's version of Alice in Wonderland, the psychedelic sci-fi Alice 2009, featured Dr. Dee and Dr. Dum, who were German-accented overweight bald old men in spandex jumpsuits, Creepy Twins torture-technicians specializing in extracting confessions from especially difficult cases. Their eerie narration to each other perfectly matches the page narration above...doesn't it, Dr. Dee? Indeed it does, Dr. Dum.
From the Redwall book Lord Brocktree, came the searat brothers Ripfang and Doomeye. Ripfang was the smarter and eviller one, going into evil for himself after the book, while Doomeye was dumber, but an absolute ace sharpshooter.
There are other instances of this trope in Redwall books as well, but rarely where the bad guys are effectual enough to really bring this trope into play, such as with the vermin pair of Dingeye and Thura in Salamandastron or Blacktooth and Splitnose in Mossflower. In both cases, the ineffectualness of them makes them more Those Two Guys straight up, rather than this trope.
