Archvillain: the Blue Freak teams up with Mad Mask in the second book. Naturally, Mad Mask betrays him and he has to team up with Mighty Mike to stop him.
In Taylor Anderson's Destroyermen, this is a fear of the Grand Alliance should their two enemies (the Japanese-aided Grik and the HolyDominion) find out about each other. While they admit that the thoroughly racist Doms wouldn't even consider allying with such vile creatures as the Grik, they wouldn't put it past Hisashi Kurokawa or the Celestial Mother to offer the Dominion a chance to join the Hunt. By the end of Storm Surge, both of the enemies are aware of one another. The Doms intend to send an expedition across the Atlantic to see if the Grik can somehow be subverted to serve their "holy" purpose. Of course, the "Grand Alliance of all Allied powers united beneath (or beside) the Banner of the Trees" is the heroic version of this. Originally made up of the crew of the USS Walker and several Lemurian Homes, it now includes most of the known Lemurians, several more crossed-over crews, the Empire of New Britain Isles, and the Republic of Real People. Additionally, another potential new ally is found, the United States.
Gone: In Lies, Caine and Zil team up to burn down Perdido Beach, which acts as a distraction to let Caine escape to the island.
Voldemort is capable of recruiting the Acromantulas, the Giants and the Dementors to his army, apart from his own dark wizard servants the Death Eaters.
As individuals, during Delores Umbridge's reign of terror in Hogwarts she allies with Crusty Caretaker Finch and most Slytherin bullies like Draco and his minions. All teachers hate her though, even Snape.
Johannes Cabal: The demon Ratuth Slabuth grants the Red Queen, aka Lady Ninuka, tremendous magical power for free because they both want Revenge against Johannes.
John Carter of Mars: In The Warlord of Mars, Matai Shang (a previously-offscreen but often mentioned chessmaster), Thurid (a minor villain from the previous book) and Salensus Oll (a newly-introduced Evil Overlord) pull off one of these, which ends up falling apart messily, since all three hate each others' guts and have only temporarily-related goals. Rounding out the partnership is Matai Shang's daughter Phaidor, though she's genuinely loyal to her dad and is mostly along for the ride rather than a co-conspirator.
In the Jules de Grandin novel The Devil's Bride, the Soviet Union funds the Union of the Militant Godless which is an alliance where anarchist atheists have joined forces with Leopard Men cults, Kali-worshipping Thuggees, Satanists and Yezidees in an effort to destroy Christianity and other mainstream religions. Yeah it was politically incorrect and factually inaccurate, but it was from 1932.
In Loyal Enemies, the Big Bad turns out to be a team of separate villains working together for a common goal and doing their best to off the heroes. There's Tairinn, Veres' ex-girlfriend who was once (correctly) accused of practicing dark forms of necromancy, and Etvor, a psychopathic werewolf, as well as a rogue monster hunter and his former apprentice who once tortured Shelena for hours, if not days, just for the sake of it.
Reign of the Seven Spellblades: Technically more of an Antagonist Team-Up. In volume 7, three of Oliver's previously defeated class rivals—Richard Andrews, Joseph Albright, and Tullio Rossi—team up for the combat leagues, hoping for a rematch. Their wish is ultimately granted in volume 9 when they wind up the co-finalists opposite Oliver, Nanao, and Yuri Leik.
In Shipbreaker Nailer's Archnemesis Dad, Richard Lopez, and Nita's Evil Uncle Pyce come to some sort of agreement offscreen that sees Richard joining the crew of Pyce's ship, the Pole Star.
The fourth Skulduggery Pleasant book see's the 'Revenger's Club' created, a group of various nefarious figures from the previous books who have tentatively teamed up under the Big Bad who's promised them each their personal vengeance on the protagonists. It doesn't last very long.
In the Star Trek Novel 'Verse, Villain Team Up is the idea behind the Star Trek: Typhon Pact series, though it's uncertain if the Typhon Pact is an enemy of the United Federation of Planets or not. Politically, everything is highly uncertain, following the formation of the Pact in A Singular Destiny. While the Pact members were historically antagonistic, their outlook is changing, at least in some cases.
The Silmarillion: Morgoth convinces Ungoliant (the Giant Spider of unknown origin) to team-up for the destruction of the Two Trees that gave light to Arda, in exchange for giving her anything she wanted in return. Ungoliant drinks the light out of the Trees and kills them, submerging the world in darkness. When she demands the Silmarils in payment, he refuses, causing the battle between the two.
The Lord of the Rings: Saruman manages to bring the Southern Men and the Pirates into an alliance serving Sauron. Unlike the Orcs and Trolls, the two groups are not bound to Sauron's magic and influence and were already a threat on their own.
In Twilight Sparkle and the Crystal Heart Spell, Trixie and Gilda have become partners in crime since we last saw them, though for the moment they're just pulling pranks, conning crystal ponies, and giving Twilight bad advice.
The Omen Of The Starsarc of Warrior Cats features all the villains who were killed off except Scourge and Bone teaming up to destroy the clans.
