A villain of Russian folklore, a wizard or demon with a penchant for kidnapping maidens. Koshchei (also spelled Koshchey or Kashchei) is found in the tale of the Firebird and the story of Marya Morevna; as both feature Ivan Tsarevitch as the hero and kill off various people, it's probable that one just reuses the characters of the other.
In the Firebird, Koshchei is something of a robber baron. He lives in a castle, kidnaps princesses and turns their hearts to wood, and imprisons the phoenix itself.
Unusually genial for a scion of evil, he tells Ivan exactly where he can find the firebird, which appears to have been stolen again by the Baba Yaga. When Ivan returns with the bird, Koshchei forces him to decide whether he'll take the phoenix or the girl home and then sneakily tries to zombify him. The princess, one Vasilisa, bursts into tears at this. Koshchei's magic had hidden her heart in her tears, and she recovers her emotions. Something about this is apparently lethal to Koshchei, because he finally dies. Obviously, the rest of the story does not concern him.
Koshchei is less of a stereotypical evil wizard in the story of Marya Morevna. Not only does he own a talking horse and a handkerchief which creates magical bridges in midair, he's a swordsman and survivor without peer.
In this story, Koshchei is introduced hanging chained on a a wall in the palace of the warrior princess Marya Morevna. He's been there for a decade without food or water, and entreats Ivan Tsarevitch, who has just married Marya, to give him some water to drink. Koshchei drinks three buckets and recovers his strength. Breaking the chains which hold him, he kidnaps Marya and flees to his palace.
When Ivan comes in search of his wife, Koshchei is away. When the wizard finds out that Marya has been freed, he asks his horse if they can catch up; the reply is an emphatic yes. Koshchei lets Ivan go twice to repay his debt. The third time, he dismembers Ivan and throws the barrel containing his remains into the sea. Ivan's sisters' husbands, however, are also wizards of some sort, and they return him to life.
Meanwhile, Koshchei is induced to tell Marya where he got the horse from. She steals his handkerchief and gives it to Ivan, telling him to tend the herds of the Baba Yaga for three days to get his own super-horse. Ivan gets the horse, causing the death of the witch in the process, and returns.
This time, Ivan gets away with Marya. Koshchei again asks his horse if they can catch up, and the reply is one of the funniest lines in Russian literature: "God knows -- now Prince Ivan has a better horse than I." Koshchei manages to reach them, though, and is about to go after Ivan again when the prince's horse kicks him. Ivan proceeds to finish the Deathless off with a club, burns the corpse, and throws the ashes to the wind. He and Marya live happily ever after.
The second story is much more complex than the Firebird, though I don't know which came first. The similarities are striking, especially the involvement of the Baba Yaga and the eventual demise of Koshchei in both. He's definitely an interesting villain, though.
Koshchei is also thought to be an inspiration for the lich of Dungeons and Dragons and other roleplaying games -- a powerful, immortal (or already dead) mage.
Updates:
Gritchka informs me that the best rendering of the name in English is Koshchei, and changed the node title to reflect it. Thanks -- I don't speak Russian, I'd found this node empty and wanted to fill it. (Plus, Koshchei is just too good not to be written up).
TheLady says that Koshchei appears in several other folktales, much like the Baba Yaga. In most of these, apparently, he's immortal from hiding his heart somewhere else (phylactery anyone?), and the goal of the hero is to destroy his heart. Many thanks.
Damodred echoes TheLady on Koschei's hidden heart, and notes that "Koshchei" actually means "Boney" or "He of the Bones." Again, thanks.
Jurph notes that Koshchei is mentioned in Neil Gaiman's The Sandman comic, in which one character boasts of stealing his heart, which here is an emerald. Thanks.
Sources:
The Red Fairy Book, by Andrew Lang: http://www.mainlesson.com/display.php?author=lang&book=red&story=death
The Firebird: www.bgfl.org/bgfl/activities/intranet/ks1/english/ story_telling/firebird/documents/text.doc
Rec.games.frp.dnd FAQ - Literary Sources of D&D: http://www.geocities.com/rgfdfaq/sources.html