The Pillar Men from Jojos Bizarre Adventure Part 2 have known each other for millennia; it's no surprise they like each other (except for Santana, who the others see as kind of a weak tool). Esidisi was even willing to sacrifice his life so that his comrades' plans could succeed.
Some of the Akatsuki duos in Naruto end up like this, but the most obvious are Konan and Nagato, who were actually friends prior to joining Akatsuki, and as such are actual friends instead of being forced to work with each other.
To put it in perspective, the other three generals are afraid of reporting failure to Lordgenome because they know it might mean their lives, whereas Guame can get away with openly questioning his orders in front of the others.
Played with in Zeta Gundam. Sociopathic Soldier Yazan Gable is clearly incapable of showing empathy or actually caring about anybody. But it's just as obvious that he enjoys the company of likeminded psychopaths Dunkel Cooper and Ramsus Hasa and Big Bad Paptimus Scirocco, playing the Manly Man to the latter's Sensitive Guy.
Sarah Zabiarov is shown to have a bad case of hero-worship and/or heavy crush on Scirocco, which he naturally exploits whenever necessary. However, there is a hint that Scirocco may have cared for Sarah more than his other pawns, as when she dies, he completely loses control and goes ballistic, the only time in the series he does so.
In Yu-Gi-Oh!, Marik's relationship with Rashid (his foster brother as well as his second-in-command) is complicated. The two are very close, and Rashid does show Undying Loyalty to his brother, but this is for a very good reason: Rashid knows that he is the only one preventing Marik's even darker personality (who killed their father) from taking hold. When Yami Marik does eventually take over, he tries to kill Rashid to prevent the real Marik from regaining control, but Rashid refuses to desert the real Marik, and this plays a vital role in the Final Battle between the villain and the Pharaoh.
Reiner Braun and Bertolt Hoover from Attack on Titan are devoted friends, and make for an extremely dangerous team as a result. They are fiercelyprotective of each other, and won't hesitate to risk their own life to help the other. Their friendship with their aloof partner, Annie Leonhart, is a bit more complicated. Even more complicated is their friendship with the other members of the 104th, who they genuinely consider their friends regardless of being on the opposite side of the conflict.
Gundam SEED Destiny reveals that Big Bad Gilbert Durandal had a functioning friendship with his predecessor, Rau Le Creuset. In fact, most of Durandal's actions are driven by his inability to prevent Le Creuset's spiral into madness.
The Team Rocket Trio of Jessi, James, and Meowth from Pokémon. They genuinely care about each other and their Pokémon. In one episode it was shown that Meowth was not treated well by them. In almost every other episode however, they treat him as a true friend.
The Incredible Hulk give us Abomination and The Leader, who became friends through their mutual hatred of the Hulk. Leader was even upset when the Red Hulk killed Abomination.
In as much as either of them is capable of it, Lex Luthor and The Joker are friends. They understand one another better than any other villains do, and despite their many fallings out, they'll always work together again.
The page image is a variant cover from Sonic the Hedgehog/Mega Man: Worlds Collide, where Dr. Eggman and Dr. Wily start the Crisis Crossover because they find a mutual friend and kindred spirit in one another. The partnership works out very well up until late in the series: the stress of their failure to stop Sonic and Megaman, despite their teamup, combined with the fact that Dr. Eggman is a murderous psychopath who will casually throw Dr. Light to his death from their vessel once he decides Dr. Light is too dangerous to keep alive, which offends Dr. Wily because A: he considers that going too far and B: he wanted to keep Dr. Light alive to rub his triumph in Light's face, causes an irreconcilable break-up between the villains. They promptly start double-crossing each other and further ruin their efforts to stop Sonic and Megaman.
Poison Ivy and Harley Quinn are genuine friends.
In Mega Man Reawakened, Glyde and Bass are friends, and later, so are Glyde and Wily. Glyde even paid Wily's billion dollar bail.
In The Lion King Adventures, Timon and Pumbaa are turned into evil beings who drain the souls of cubs to preserve their immortality; however, they are still just as much friends as they were in the actual films.
Films — Animated
Maybe they're a bit more like pets, but when Ursula accidentally zaps Jetsam and Flotsam in The Little Mermaid, she looks absolutely distraught and decides to go One-Winged Angel.
In The Dark Knight Rises, it is revealed that Bane is merely The Dragon to the real Big Bad, Talia Al Ghul. Their backstory swiftly reveals that he pledged his life to protecting her when she was a little girl in a Hell Hole Prison, and it's likely that Talia is the only person Bane has ever cared about, to the point that he was willing to fight off almost all of the other inmates, suffering an agonising disfigurement in the process, just so that she could have the freedom that was denied to him. And she came back for him, bringing the might of the League of Shadows to bear against the prisoners who injured Bane and murdered Talia's mother, asking Ra's to spare Bane. Their relationship has been one of absolute loyalty and mutual trust ever since.
In The Dark Knight, the Chechen and Maroni are clearly good friends outside of work. They're even having dinner together when they're arrested.
Calvin Candie and Stephen in Django Unchained are shown to be genuine friends, with Stephen, the head house-slave, preserving Candie's authority at Candieland and basically running his plantation for him, and Candie providing Stephen with a dominant position in his organization.
Cohaagen and Hauser (Quaid's former identity) in Total Recall (1990). Cohaagen acknowledges their friendship when Quaid calls the guy an asshole and makes sure he is given an obedient, mindwiped wife to "enjoy", goes into a rage when he is forced to order the death of his friend, and goes on a tirade against Quaid for making sure he's not coming back.
In Scarface (1983), Tony Montana and his eventual Dragon Manny Ribera start out the film as friends, which doesn't change as they start a criminal empire in Miami. Manny eventually gets fed up with Tony's more malicious behavior, like beating up his sister's touchy boyfriend. When Manny secretly elopes with Tony's sister, his friend goes nuts and kills Manny in a jealous rage.
Drug kingpin Nino Brown in New Jack City has a friendship with his lieutenant Gee Money that doesn't seem to be faked. When they establish their criminal empire, Nino tells Gee that they've finally made it and that they have to look out for each other. Near the end, he expresses his friendship with Gee as more important to him than all the money and women he has gotten, but they just can't go back to the way they were after Gee betrays Nino by making a deal behind his back. Nino struggles to kill Gee as tears roll down his face.
Gothika: The serial killer/rapist is eventually revealed to have had an accomplice. After Sherrif Ryan is revealed as Doug's accomplice, he states that he helped Doug out with his first kill because they were friends, and since then they have been destroying countless lives for their depraved gratification. Ryan goes on a rampage against Miranda as revenge for killing Doug (she was possessed by the ghost of one of the victims).
In the first Batman film, directed by Tim Burton, The Joker and his right-hand man Bob seemed to have a pretty good relationship. Bob was the second in command of The Joker's group of thugs back when he was Jack Napier. After Jack's transformation into The Joker, Bob stayed by his side as his loyal right hand man. Bob was very loyal to his boss and did everything he was asked with a "Yes sir!" The Joker seemed to value his loyalty pretty well, telling him "you are my number one guy". But that all ended when The Joker shot and killed Bob just to vent his anger after Batman foiled one of his plans.
Harry and Marv from the Home Alone films seem to have a pretty good friendship, despite Harry often getting annoyed with Marv's stupidity. In a deleted scene, the two are even shown singing "Harry And Marv are coming to town".
Implied to be the case between Nicodemus and Anduriel, the Fallen Angel that shares his body, in The Dresden Files. While most of the Denarians (the organization Nicodemus heads) end up little better than slaves to their Fallen before long, the fact that Nicodemus has retained his free will and humanity despite being possessed for approx. two thousand years speaks of at the very least a healthy respect between them. Part of the reason it works is that Nick is horrible enough on his own that he doesn't really need much demonic prompting...
In the Honor Harrington series'', Rob Pierre and Oscar St-Just are friends aside from being loyal, while they recognize they are two very different personalities. David Weber often shows this type of relationship between people on the opposing side of his heroes, as he often has the "villains" be doing things for reasons other than just purely For the Evulz.
Tony Soprano of The Sopranos with Silvio Dante and Paulie Gualtieri.
Avon Barksdale and Stringer Bell from The Wire have been friends since they were kids, and as of the show's first season they have killed and plotted their way into controlling the drug trade on the West Side of Baltimore. However, they begin to grow apart after the end of Season 1, when Avon is arrested and sent to jail while Stringer avoids any jail time, as Stringer has very different ideas about running the business. Stringer wants to run the illegal drug trade like a business, without the violence and Mob Wars, while Avon exults in everything that is part of The Game, especially his reputation and the taking of turf. Eventually they both reluctantly turn on each other, with neither knowing that the other was also doing a set up. The result is that at the end of Season 3 Stringer dies and Avon goes to jail again.
Justified has Wynn Duffy and his bodyguard and enforcer, Mike, who live together in Wynn's trailer, and always look out for one another. There's also Dickie Bennett and Dewey Crowe, who are always overjoyed to see each other, and go out of their way to protect one another when in jail together.
Brock Lesnar and Paul Heyman. Despite being Heels, the two do genuinely care about each other. In the 2013 Extreme rules match against Triple H, when Trips had Brock in a submission he had no chance of escaping, Paul rushed into the cage to help Brock knowing that he stood no chance against Trips, allowing Brock to defeat him. In one interview, Heyman described a meeting with Brock where Brock showed him a picture of their kids playing together. Lesnar was also the one who asked Heyman to be brought back to the WWE.
The Pathfinder adventure path "Legacy of Fire" posits a close friendship between gnoll assassin Rokova and troglodyteclericGrundmoch, despite the fact that both of them are Chaotic Evil servants of Rovagug. This actually becomes a plot point, for when evil genie Zayifid kills and replaces Rokova, Grundmoch notices, outs the genie to the PCs, and is actually quite willing to ally with them if it means Zayifid ends up dead. A Spanner in the Works caused by friendship between monsters. Not something you see everyday.
Grundmoch actually seems to have a talent for this. His personal bodyguard is a gibbering mouther called The Gargler, which the text notes he has managed to not only train, but befriend. The Gargler is loyal to Grundmoch, and will attack anyone who threatens him without any regard for its own safety.
It should be noted that even though Dracula does use Soul Steal on Death once (in the aforementioned Portrait of Ruin), Death told him to do it as a last-ditch effort to defeat Johnathan and Charlotte.
Touhou: Toyosatomimi-no-Miko and Mononobe-no-Futo, the scheming immortals.
Shezar and Mudou in Duel Savior Destiny tend to fight a lot and threaten to kill each other, but considering their personalities, the fact that they haven't done it is a pretty good indication of their friendship. When Mudou dies before Shezar in Mia's route, he's the only one of the bad guys to actually get upset about an ally falling while the rest of them basically shrug and call him replaceable.
The demons Decarabia and Forneus of the Ars Goetia aren't mentioned in the original text as having any relationship to each other, but are best friends in two out of five the Shin Megami Tensei games in which they both appear, even getting a combination attack together in Persona 3. Probably because, again unlike in the Goetia, they're both depicted as sea creatures, a starfish and a ray respectively.note According to the Ars Goetia, Forneus was a "great sea monster" — with no further description of what he was beyond that — and Decarabia was a pentagram that could take human form. As such, he's usually portrayed in other media as either a starfish or an animate magic circle. It more or less started in Shin Megami Tensei III: Nocturne, where Decarabia's found waiting for Forneus at the site of the Hachiko statue.
WildStar has the Draken and the "Chua." The former love killing things. The latter dedicate their lives to making better, more efficient ways of killing things. They got along nicely.
Albert Wesker and William Birkin from Resident Evil, at least as much as two sociopaths could be. Placed in charge of one of Umbrella's facilities as teenagers, the two were noted to be close and conspired together on many occasions. Their partnership remained well into their 30s, with Birkin actively aiding in Wesker's plan to betray Umbrella and steal their research. Birkin's death at the hands of Umbrella agents seems to have genuinely made Wesker very cross, something rare for a man infamous for using and throwing people away.
Ellen and The Demon from The Witch's House share a... complicated relationship. On one hand, they seem to mostly be working toward their own goals, Ellen often gets annoyed with The Demon, and he is willing to pull a You Have Failed Me on Ellen. On the other hand, they do seem to get along over their shared love of evil, and The Demon usually greets her in a friendly way, often addressing her with a "Yo". In one of the game's endings, he addresses Ellen as "My fair witch", he taught her how to read and write, and instead of pulling a You Have Outlived Your Usefulness he kept his part of their deal.
Homestuck: Jack Noir and the Draconian Dignitary, as seen here and the next page. They seem to actually be Moirails (compare with the definition of Moirallegiance here).
Goblins has Dellyn Goblinslayer and his dragon Sarral Caine, two evil adventuring buddies who've been through thick and thin together. Dellyn considers Caine to be the only person around that can be depended on, and is visibly shocked and grief-stricken when he finds Caine's body.
The Order of the Stick: In the earlier strips, Xykon and Redcloak appeared to be an example of Type I, but they are actually a Type IV, with Xykon being horribly abusive to Redcloak and Redcloak thinking Xykon is the most depraved and disgusting individual he has ever met and secretly manipulating him for his own ends (Xykon is much more overt about it). They still laughed over tormenting heroes and minions, but eventually this leads to a Villainous BSOD for Redcloak when he realizes that Xykon has become a seriously bad influence on him in terms of how he treats his own minions.
Tarquin and Malack, meanwhile, appear to be a straighter example of a Type I, as seen here.
Tarquin's entire evil adventuring party seems to run on this. After all, his ploy to conquer the Western Continent wouldn't work without cooperation and respect, and more to the point, when Nale is gloating over killing Malack, Laurin is horrified and enraged, while Tarquin himself goes into a Tranquil Furybefore killing Nale. Maybe subverted, as he was perfectly willing to let it slip if Nale was willing to become Tarquin's pawn.
"What did you think the price for killing my best friend was going to be?"
Further, Tarquin and Miron are close enough for the latter to give the former a nickname ("Tarkie"), and Laurin's daughter installed a bidet for Miron's boss.
Thog's relationship with Nale seems to be a Type III — Thog explains to Elan at one point exactly why he thinks of Nale as his friend, but Word of God is that Nale keeps Thog around only because of Thog's combat ability and has no real concern for him. At the same time, Nale's relationship with Sabine would be another Type I, if they weren't actually another trope.
Nale does seem to have a genuine Type I relationship with Drow Wizard, Zz'dtri, with them showing a surprising loyalty towards each other. Nale ends up being genuinely horrified when the latter is killed, even trying to save him before being forced to flee.
Similar to the Thog/Nale example, the Monster in the Darkness' relationship with the rest of Team Evil appears to be a Type III. He definitely thinks of them as his friends, but they only tolerate him in order to use him as a secret weapon.
Redcloak does seem to have a genuine Type I with his own Hobgoblin lieutenant Jirix — even if they're not outright friends, they do have a healthy respect for each other, and definitely get along better than Redcloak does with Xykon. It's an improvement over his previous Type III, where the Hobgoblins were fanatically loyal to Redcloak but Redcloak thought Hobgoblins were less than dirt, until one died to save his life, that is.
Tsukiko's relationship with Xykon is a definite Type III. She's in love with him, but he couldn't care less about her and thus is indifferent when Redcloak puts her to death.
Back when he was a young human, Xykon had a genuine one with fellow apprentice Yydranna. He accepted her being chosen as their boss's Dragon over him, she gave him advice about his tendency to go with raw power over tactics, and they parted on pretty good terms for mass-murderers.
Yydranna: If I'll ever see you again, I'll have to ruthlessly crush you.
Xykon: I'd be disappointed if you didn't try.
While Moist in Dr. Horrible's Sing-Along Blog arguably qualifies as Horrible's Dragon more just by default than anything, the two are clearly best friends as well as supervillain and (only) henchman.
Rich Burlew (author of The Order of the Stick) wrote an article on giving TTRPG villains personalities that extended beyond acting purely to further the plan. The example he gave was a campaign in which two villains who were working together and whom the heroes fully expected to backstab each other, because they just couldn't believe that the villains really were best friends.
In The Irate Gamer, Evil Gamer and Satan seem to be pretty good friends. In the Zombies Ate My Neighbors review, Satan and Evil Gamer were shown having a friendly conversation in Hell, and Satan even agreed to bring Evil Gamer back to life. In the Monster Party review, Satan and Evil Gamer made a deal where evil would help Satan get to Earth so he could Take Over the World if Satan killed the Irate Gamer. Satan ended up befriending Irate Gamer instead and went to hang out with him and Ronnie at a bar. Evil got mad at Satan for not killing the Irate Gamer, but Satan suggested that they all Go Karting with Bowser, even offering to get Evil Gamer some cheesecake. In the Silver Surfer review, Satan congratulates Evil Gamer for thinking of a robot invasion before he did.
He-Man and the Masters of the Universe (1983): Seen with some of Skeletor's henchmen, oddly enough. It's most obvious with Trap-jaw and Whiplash's friendship (which comes across as Whiplash having a rather one-sided boy crush on Trap-Jaw), but Webstor and Kobra Khan seem to get along quite well also. Tragically, I don't think we'll ever know how Khan really felt about his Snakemen buddies killing Webstor in the 2002 series.
The Psycho Rangers in Book 3: Change all get along very well. Zaheer and Gahazan give each other a firm handshake upon meeting each other again (and friendly chatter on how Zaheer gained airbending following Harmonic Convergence, Ming-Hua light-heartedly teases their "ugly mugs" but is very grateful to see them when they spring her, and jokes about how they rescued her before Zaheer's girlfriend.
Megatron and Soundwave of the various Transformers franchises definitely qualify. In fact, when reborn as Galvatron, Megatron showed open grief and rage at Soundwave's death, and cared enough for him to bring him back to life.
Transformers Prime has Breakdown and Knock Out, The Brute and the Deadly Doctor respectively, who are in fact extremely good friends. Knock Out takes Breakdown's demise and Silas' use of his corpse as a cyborg body very, very badly. Knock Out and Starscream also qualify, since they share a mix of Evil Genius, Butt Monkey, and Dirty Coward traits and easily sympathize with each other as intelligent but rather histrionic villains.
While not exactly "villains", Diamond Tiara and Silver Spoon of My Little Pony:Friendship Is Magic are two friends who love to bully and antagonize the Cutie Mark Crusaders, and they are always antagonists in episodes where they play a role.
Pinky and the Brain are Well-Intentioned Extremist s trying to Take Over the World to make things better. Pinky obviously cares a lot about Brain, viewing him as a true friend. Brain often gets annoyed with Pinky and harms him, but despite this, he does in fact care about him. When Pinky sold his soul to get Brain the world in "A Pinky And The Brain Halloween", Brain rescued him because he missed him and ruling the world was no fun without him. In the Christmas episode, Brain tears up when he finds out that Pinky wrote a letter to Santa asking for Brain to be given more respect.