What to use here would depend on how you're translating the story, overall. Is it supposed to "sound Russian" at all? If so, then you could write, here, "He looked like the fairytale ogre Kashchey the Deathless..." That both includes a Russian name of the figure, and explains who he is.

If you want to sound entirely Western/American/English, just write, "He looked like some kind of threatening figure from a fairy tale." Myself, I like the generic "fairytale ogre," without bothering to name him.

--------------------------------------------------
Note added at 12 hrs (2009-12-02 11:11:34 GMT)
--------------------------------------------------

P.S. to Victor Yatsenko

I considered suggesting the Old Man of the Sea, the scrawny character who had killed many sailors before Sinbad the Sailor dispatched him. When I was a kid, I thought the Old Man of the Sea was just about the most evil, scary character in any book. There's a problem with this creature, however, caused by Hemingway. I think at least half the readers would see "the Old Man of the Sea" and "hear" "The Old Man and the Sea."

--------------------------------------------------
Note added at 17 hrs (2009-12-02 16:17:27 GMT)
--------------------------------------------------

Further thought... If you mainly want to get the physical image, you could do a more precise descriptive translation: "... looked like a creepy, skinny old man in a fairy tale."