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. They also sometimes refer to themselves as "the greatest killers in all spacetime", which lampshades their archetypal nature.
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?". Their title of "The New Firm" is also a clear nod to Coup & Vandemar of Neverwhere.
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.
Cathy and Anna from SeaFire. At one point, they disguise themselves as men and put on an exaggerated act of being duo of killers who talk to each other very formally and dress impeccably.
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.
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.
The Duke and the King 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.
Götz 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 Knight Templars.
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 who serve as the personal assistants of Inquisitor Glokta. They're like secretaries. Scary, twisted secretaries. Severard is an affable and talkative Satisfied Street Rat and Frost is a hulking, usually quiet brute- subverting Dumb Muscle, he has a Speech Impediment, but is a Deadpan Snarker and apparently has beautiful and elegant handwriting.
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.
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.
Skulduggery Pleasant: Vaurien Scapegrace, a dim-witted zombie with plans for world domination, and his minion Thrasher.
The Towers Trilogy has Torrence and Daye, a pair of mercenaries who Xhea once worked with but who are now employed by her enemies. Torrence is chatty and expressive, while Daye is terse and emotionless.