Hwa Ryun from Tower Of God. While she is a pretty laid back person who can even forgive Baam for cutting out her eye in self-defense, she is part of the conspiracy. That means she was well aware of the cruelties that lay ahead of out cute little protagonist and even contributed to these plans.
While not so much evil as "egotistical", flame-haired Maaya Nanako of Umisho claims to be leading male Kaname's Unlucky Childhood Friend. His memories of her are not at all pleasant.
In the third volume of the manga, Nao actually assists the other HiMEs by luring Nagi into a trap after their escape from a cavern deep underneath Fuuka. Of course, she says she's not doing it forthem.
Aside from Fuku (who never attacks the Mermaid Princesses directly, anyway), the first real member of Michel's Winged Ones who shows up is LadyBat, who also has burgundy red hair.
Kaolinite, Eudial, Mimete, and Cyprine, all from the Witches 5, in the third season.
VesVes the Tamer in the fourth season. At least she has the excuse that the Quirky Miniboss Squad to which she belongs is themed after the colours of the senshi. Strangely, though, the exception is CereCere the Illusionist, who is given pink instead of orange.
And Akane Karasuma, aka Sailor Lead Crow, in the fifth. Also a Dark Skinned Redhead.
Arnage of Huckebein from Force plays it straighter (thus far?).
In Naruto, there are five red-headed villains to date, Gaara (before his Heel Face Turn), Jiroubo, Tayuya, Sasori, and Pain (which includes both Yahiko, who was a good guy when he was alive [orange], and Nagato, the actual controller [blood red].)
Though she's not as evil as the other villains, Karin could qualify as well.
Subverted with Kushina, Naruto's mother.
Recoome of the Ginyu Force and movie villain Bojack from Dragon Ball Z. When the latter transforms, his hair actually gets redder.
Subverted by Android 16, a red-mohawked Friend To All Living Things (but Goku).
Goki, The Mole from the manga series Kagerou-Nostalgia. A nearly emotionless killer completely in thrall to the Big Bad, he convinces the heroes that he is one of them (not hard given his status as the Reincarnation of one of their former allies) and proceeds to murder their leader before defecting back to the villains. He appears to have some regrets about this now.
Due to her...special shade of hair color, she could also count as Blondes are Evil.
Eustass Kidd in One Piece. The argument that he was just a Jerkass and not evil can be thrown out once you learn he has impaled people with glee once he's in the New World.
Momomi Minoi, the Cute and PsychoYakuza Princess from Mezzo Forte fits quite well. One of her recreational activities seems to be casually murdering her father's employees when they fail to meet her expectations...and that's just when she's having fun. If someone actually tries to get in her way, she will do her best to ensure that they experience far worse.
Kakyoin from JoJo's Bizarre Adventure was one at first, but Jotaro 'snapped him out of it'. Later on, Dio tries to confuse the heroes through one of his assassins, a shapeshifter, into thinking Kakyoin went back. There are a couple of other characters or so, though: Midler in the video game is depicted as a redhead and Big Bad Diavolo's hair is coloured magenta. Or something.
The Ranma ½ anime gets an episode full of this trope. When Happosai splits Ranma's male side and female side into two different people, the female side turns out to be evil to the core. The glowing eyes, floating red hair, and supernatural powers certainly don't hurt in making her seem any less sinister.
Akakabuto from Ginga Nagareboshi Gin is named for the red patch of fur on his head. Heck, his name even means "Red Helmet"!
Played with by Kyouko in Puella Magi Madoka Magica. She's the only redhead in the cast, and is easily the most amoral and violent, but Sayaka's influence causes her to evolve into more of an Anti-Hero. She was originally an overtly heroic person like Sayaka, until her Deal with the Devil convinced her religious father that she was an evil witch, and he killed himself and the rest of her family. After that, she decided to be completely selfish to avoid hurting people she cared about...by not having any.
Touga Kiryuu in Revolutionary Girl Utena. He tricks his sister Nanami into thinking they weren't blood siblings and that he never loved her, even though they were just merely adopted by into the same family and Nanami was too young to be able to remember. Also, he gets his friend Saionji expelled from school and burns the exchange diary right after Saionji entrusted it to him
Also in X-Men, Cain Marko, aka Juggernaut, is a redhead, though it's rarely explicitly shown thanks to his signature helmet of psi blockage.
Then there's Belasco, the red-haired, devil-horned sorcerer who stole Illyana Rasputin's childhood.
And the shape-changing Mystique, whose default body is a combination of blue skin and red hair. Her adoptive daughter, auburn-haired Rogue, starts out as a villain (the Scarlet Witch's hair has pretty much the same shade).
Aversion: Thomas is the evil member of the Cassidy family. Sean and Theresa are redhaired and heroic, while Black Tom has black hair.
Also, Hush, one of Bruce's childhood friends, introduced rather recently (and has taken The Only One Allowed to Defeat You route as of Detective Comics #846).
The Scarecrow and The Riddler can be redheads depending on the artist.
Lex Luthor usually has red hair, when he has hair. In fact, he didn't lose his hair until his fifth generation.
Lightning Lord, older brother of the Ranzz siblings of Legion fame...although his more iconic look is from after his hair has turned white.
Based on the cover art and the video game, Scott Pilgrim's ex-girlfriend Envy is one, though they made her blonde in the movie. To be fair, her "evilness" isn't so clear-cut, as we learn what an Unreliable Narrator Scott is.
Batman: Jason Todd was retconned into being a redhead. Batman apparently made him dye his hair black to hide the fact that the role of Robin had gone to someone else.
Kainatrol in Futari Wa Pretty Cure Blue Moon has deep red hair and a red colour scheme, and is probably one of the more evil members of the Etherium and certainly the least likable. Even the first on-screen victim of her Mind-Control Eyes, Mia, had red hair. (On the other hand, there's also Dawn.)
Randal Graves of the View Askewniverse could fit in here somewhat. Although he isn't technically evil, he thinks nothing of spitting water in customers' faces, ordering porno titles in front of children, manipulating his best friend into horrible but brilliant verbal traps, indirectly destroying several of said friend's romantic relationships, and generally causing chaos and frustration wherever he goes. And when he's not in black and white, he is titian-haired (dirty red-blonde).
Alice in Wonderland: The Red Queen. The Mad Hatter subverts the trope; he can certainly be pretty menacing at times, but he's unquestionably one of the good guys.
In Gremlins 2 The New Batch, there's a scheming female boss who tries to seduce Billy and is a Jerk Ass to Kate. She ends up being trapped in Spider Gremlin's web! Guess who saves her bacon...
Literature
Pictured above: Melisandre of A Song of Ice and Fire is an marginal example. As a Knight Templar priestess who worships a fire-themed god and often recommends human sacrifice by burning, she's regarded by many characters as an Evil Chancellor. However, she's also firmly committed to fighting the overtly evil Others, believing that the brutal actions she recommends are necessary for the greater good of humanity. Ultimately, her morality is somewhat debatable.
Anne Rice's Vampire Chronicles has many red-haired vampires. Most notably, Maharet and her scary-as-hell sister Mekare - though the yandere-like Armand arguably fits the bill too. Maharet, however, is nothing approaching evil (apart from being a vampire, which she was made into against her will).
In the Illuminatus! trilogy, Satan prefers redheads and they explore this trope in depth.
Well, it's a reference to old folk-beliefs. It works because the Black Mass participants believe it should. In an inversion, one of the participants is a protagonist who is taking his first steps in his path away from social conventions towards illumination. He and the redhead get some good sex out of the deal and get to meet Malaclypse the Elder disguised as Satan disguised as Billy Graham.
Lampshaded in the short story "Nobody Here But-" by Isaac Asimov where the protagonist suspects his girlfriend is bitchy just because she has to live up to her red hair.
Celia Madden of The Damnation of Theron Ware. (Though perhaps "evil" might be a bit strong, as "bitchy" serves just as well. But it still counts.)
The ghost of Peter Quint from the Victorian novella The Turn of the Screw, who the main character thinks has come back from the dead to try and corrupt the small boy she's been charged with watching over. Of course, the ghost may just be in her head. Apparently, at the time the novel was written, it was quite common for red-haired characters to be portrayed in this villainous way.
Lumiya from the Star WarsExpanded Universe — formerly known as Shira Brie, as well as Admiral Natasi Daala. Also, judging by the images of his clones, plus some earlier life picture, Emperor Palpatine himself was one. Mara Jade counts, at least until she gets married to Luke Skywalker.
Brand from The Chronicles Of Amber, who wanted to destroy the universe and remake it in his own image. And his redheaded siblings, Bleys and Fiona, are also fairly morally dubious. To be fair to Brand, the rest of the family had its own moral issues, though by the end, some of the others had made some progress toward outgrowing it.
In The Day Of The Triffids, the protagonist is fired upon without provocation by a nameless gang leader with red hair. He later shows up in an armoured vehicle as 'Torrence', representing a despotic feudal 'government' trying to extend its influence over Britain.
In the Andrew Vachss novel Strega, unlicensed private eye Burke does a job for the titular character, the crazy flame-haired relative of a Mafia boss, who wields a mysterious power over men. It later turns out the Mafia boss molested her as a little girl; when Strega told her father, she was beaten for telling 'lies', teaching her an early lesson in power that she later puts to use.
The Lone Power, from the Young Wizards series, often appears as a young man with red(dish) hair.
In I, Coriander, Arise insists Coriander must be evil because of her red hair - "All these curls, red as the flames of Satan! This is vanity, this is pride."
In Poul Anderson's Operation Chaos, the genie tries to invoke this, abusing Ginny for having "hair like hell". She ignores it.
Sisterhood series by Fern Michaels: lawyer Adel Newsom is definitely this. It's a good thing that she's actually stupid.
Ruin, the personification of entropy, chaos, and destruction in Mistborn - while usually either shapeless or impersonating people - physically manifests as a redheaded man.
Notably, the mind of Ruin {separate from the power) was actually once a man named Ati, and a note in The Way of Kings, which is in the same Verse as Mistborn, indicates that Ati was a nice guy before he became bonded to the power and it warped his mind. So his evil had nothing to do with being a redhead and his physical body was essentially completely irrelevant. We don't even get to see his physical form until he was already dead.
In Jeeves and Wooster, this is one of the reasons Jeeves advises Bertie to steer clear of Bobbie Wickham.
"I would always hesitate to recommend as a life's companion a young lady with quite such a vivid shade of red hair. Red hair, sir, in my opinion, is dangerous."
He had said she had red hair. Well, she had; but that was no way to speak of it. When red-headed people are above a certain social grade their hair is auburn.
In Ian Fleming's Moonraker, Hugo Drax had red hair that really underscored his startling appearance.
The Dream Masters on Sliders. Very ginger and very evil.
Played with Lydia on Teen Wolf, particularly in "Lunatic." Way to blatantly manipulate Allison and Scott.
In Burn Notice, one of the most vicious female characters to date (and definitely the youngest vicious character), Eve, is played by redheaded actress Aviva. Fiona comments that she's the first natural redhead she's seen since leaving Ireland.
Criminal Minds has some red-haired UnSubs, like Karl Arnold, aka The Fox.
Both film adaptations of Dune have this going on: David Lynch's has a strawberry-blond Feyd-Rautha (played by an enthusiastic Sting in brass underpants) and the miniseries features Ian McNiece as a Baron Harkonnen rocking the henna look.
In Firefly, we have Saffron. Or Yolanda. Or Bridget. No one's sure what her real name is, we just know she has red hair.
Garth Marenghi's Darkplace has the hero battling evil Scotsmen, with his own hair turned red after a killer bagpipe attack. Fortunately, his personality is not affected (probably because he's already a bigoted Jerk Ass).
In NCIS, McGee is wooed by a North Korean-employed red-haired assassin, played by Lindy Booth. Booth seems to have the seductively evil redhead down pat.
In Supernatural, Anna Milton, who ends up fighting the blonde Mary Winchester inThe Song Remains The Same.
This was, however, a rather sad addendum to her original Heroes Want Redheads function (which was perhaps subverted in that the redhead wanted the hero!).
Semi-averted in Waterloo Road. The show's only redhead, Danielle, hangs around with Aleesha, who is pretty evil (sabotaging Park Side Story, tricking Karla into the whole petition thing). However, Danielle, to her credit, has balked at many of Aleesha's more evil schemes and actively refuses to take part in them.
Garbage's Shirley Manson sings in a rather EVIL fashion.
Well, she DID get tapped to play Catherine Weaver, as mentioned above.
And before Garbage, this was Danny Elfman's stage persona. He looks so cheerfully demonic that you have to wonder why he wasn't cast as The Joker.
David Bowie's stage persona of The Thin White Duke, a heartless aristocrat, had predominantly reddish-orange hair.
Mythology
It's a common folk belief that many evil figures in The Bible, most notably Cain and Judas Iscariot, had red hair, despite there being no textual evidence of this. In Medieval times, when most of the population was illiterate, stained-glass windows in churches would tell various stories from the Bible in picture form and red hair was used as a shorthand for evilness, since it evoked the image of fire and Hell.
Averted — actually, inverted — in Robert Graves' King Jesus, where Jesus has red hair, this being one of the eight "signs of royalty".
Straight-up subverted by David, whom Samuel was reluctant to appoint king because of his red hair, which was associated with violence and bloodshed, until God told him that David would shed much blood, but it would be that of Israel's enemies.
According to some translations of the Bible, the devil has curly red hair.
Older Than Dirt: the ancient Egyptian pantheon has the god Set, best remembered for hacking his brother Osiris into bits and scattering the pieces about the world. He was depicted as being a redhead — or at least red-furred, since he was usually depicted with the head of an unidentifiable animal.
There is some speculation about what kind of animal Set is often shown as, but it resembles an aardvark — which don't have much fur on their heads anyway.
Loki, the god of mischief in Norse Mythology, in contrast to the much more masculine Red-Headed Hero Thor. In Norse tradition, those born with red hair and blue eyes were thought to possess supernatural strength and were more likely to be harbingers of battle. The modern depiction of Thor with blond hair is wrong on multiple levels, as blonds were considered to be calmer and more strategic in battle, hence Odin's coloration.
Rumour has it that red hair was considered a positive factor in selection to become a druid - this may account for the malign reputation of red-headedness amongst those cultures that were hostile to Celts. (And probably among the Christian missionaries too.)
At least one painting of Pandora, the first-woman whose curiosity brought diseases into the world, gives her fiery red hair and a scary look on her face.
A few pre-Raphaelites depicted Salomé as a ginger, too.
Averted with King Menelaos of Homeric legend, always depicted as a redhead, because his name is Menelaos Xanthos, which means "Menelaos the Blond". Yeah, it's that sensible.
Because of the association with Judas, Shylock of The Merchant of Venice was originally portrayed as a redhead, and this was generally a common trait of "evil Jew" characters.
He's not explicitly stated to be evil, note since there isn't much canon information about him but there's something just plain off about the Happy Mask Salesman. Especially noticeable when you tell him you can't give him the Majora's Mask yet.
Aribeth has reddish hair (much more apparent from her portrait than her character model), though she is only evil for about half of the first campaign and you get to choose whether she stays evil in Hordes of the Underdark.
Tactical RPGs like Fire Emblem portray the enemy units as having red armor and hair.
Bowser from Super Mario Bros. Despite being a Koopa, he still has some hair.
Walter Bernhard from Castlevania: Lament of Innocence. And damn, does he ever have fun with the 'evil' part.
Subverted in Portrait of Ruin: Stella and Loretta are redheaded twins (though occasionally coloured with violet hair), but they're just Brainwashed and Crazy.
Partially subverted in Curse of Darkness; Isaac is completely nutters, but it's heavily implied that, half the time, Dracula is driving or at the very least co-piloting him. Isaac's a willing 'passenger', but still...
Late in Tales Of Symphonia, it is revealed that Zelos Wilder was a spy all along. However, just prior the boss fight, he defects back to the heroes' side. If you choose to talk to Kratos in an event prior to this revelation, though, you kill Zelos instead and Kratos takes his place.
Creed Graphite, the "scarlet-haired devil" from Tales Of Hearts.
Kerrigan from Starcraft had red hair, but it changed colour when she turned evil. Foreshadowing?
Blood Rayne is a Heroic Sociopath who enjoys the cruelest and most brutal means of exterminating monsters. If the kill animations weren't indicators, her dialogs with her enemies don't do much to distinguish her from them.
Triumph Studios seems to love playing with this trope in their Overlord series of games, as Rose, one of the mistresses from Overlord, is a redhead. In Overlord II, all three mistresses have hair colors that are various shades of red. However, Rose and Kelda (the most redheaded of the mistresses) are actually non-evil (Rose believes in Order and Kelda is the Victorious Childhood Friend) and arguably the Only Sane Women of the setting.
Marisa Kirisame during Story of Eastern Wonderland. That is, when she was still evil. Or redheaded.
In Trauma Team, the "Raging Bomber" is revealed to be a woman named Sandra Liebermann. When the player finally sees her in person, she's holding an airport hostage with bombs strapped to her chest, and her general appearance can only be described as "Ax CrazyUp to Eleven".
Akuma is a subversion. While his appearance just screams Obviously Evil and his powers are very much of demons, Akuma does have a code of honor when it comes to killing opponents, albeit a very skewed one. Not that he's a nice guy in the slightest, however.
Giygas from EarthBound appears to be this literally.
Neither is entirely evil per se, but Vermilion Akiha and Kohaku are both red haired, yandere, psychopathic characters in Tsukihime, and both have rather unsavory goals. Akiha is 'evil' here precisely because her hair is red, even. Kohaku is essentially the poster girl for Stepford Smiler, Break the Cutie, Emotionless Girl, and Woobie, Destroyer of Worlds.
Web Comics
Psycho for Hire Valentino from the Marilith webcomic. To her defense, she was made a psycho killer in a gulag.
Lysinda and Oasis from Sluggy Freelance. Particularly emphasized with Lysinda, who sports red hair even when the rest of the strip is in black and white.
Pompey, Vaarsuvius' second Evil Counterpart in the Linear Guild has bright red hair - part of his being an evil opposite to V involves the fact that V wears red and has purple hair while Pompey wears purple and has red hair.
Player 2. He's entierly red, but his actual hair is ginger. Also the only Player with a Beard of Evil.
Christian has dark-reddish-brown hair and a soul patch to boot.
Mal from Head Trip probably counts, although she isn't completely heartless.
Evil Diva has the red hair of the character she's supposed to have. White Sheep, unfortunately for her.
Cerise from Eerie Cuties and Magick Chicks, who is not only part of Melissa's clique, but also plots to overthrow Melissa and take over.
Bob, of Bob and George, is a LITERAL fiery redhead: his hair is red, his powers are fire-based, and when he's really pissed off, his hair tends to burst into flames. His place in the comic tends to swing between Heroic Comedic Sociopath and outright villain.
While not an actual redhead, Maxwell Lombardi has dyed red streaks in his hair. And given that he is one of the few killers in v4 to actually enjoy killing...well, he fits.
Broken Saints - Lear Dunham. His son Gabriel also has a reddish tint to his hair, at least in some lights.
The MS PaintFan AdventureAlanna has Tristan, primary antagonist and confirmed murdered. Later in the story, Alanna finds a half-empty bottle of red hair dye.
South Park did an entire episode, "Ginger Kids", where Cartman was convinced that "gingers" (pale, freckled, red-headed kids) were monstrous, Children of the Corn-like abominations. In what would have been a surprising example of Hypocritical Humor were we speaking of anyone other than Eric Cartman, after his friends tried teaching him a lesson by making him up to look like a "ginger" while he slept, Cartman soon decided that "his people" were the master race. And since this is Cartman we're talking about, he was attempting genocide before the end of the episode.
The Ginger kids return in the 200th and 201st episode and demand the town hand over Muhammad so they could obtain his ability to not get ripped on. It is revealed a now Ax Crazy Scott Tenorman is their leader. He justifiably wants revenge on Cartman for making him eat his parents. He puts him through an ordeal much like the one the Joker put Commissioner Gordon through in The Killing Joke.
Death Watch member Bo-Katan from Star Wars: The Clone Wars (since her first un-helmeted in Season 5's Eminence).
Jack Spicer from Xiaolin Showdown, Hotstreak from Static Shock, and Montana Max from Tiny Toon Adventures, all voiced by redhead Danny Cooksey, who also played red-headed antagonistic jerk Budnick on Salute Your Shorts. Perhaps Danny Cooksey himself is evil, too. Nobody knows.
If he is, he's bound to be harmless. He also lends his voice to the heroic-but-cowardly Dave from Dave The Barbarian (who, notably, is not redheaded—but his more aggressive sisters are). This overlaps with Jack's notable cowardliness, so we've little to worry about from Mr. Cooksey if he's a villainous type.
Don't forget the first appearance of his Teen Titans villain, Control Freak.
Aaand subverted with Keef on Invader Zim, who is terrifyingly nice.
Candace, from Phineas And Ferb, is a more benign example of the trope. She's not really evil per se; she just wants her brothers to get caught doing the outlandish things they do. Several episodes prove just how much she loves them.
