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.
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.
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.
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.