I like these songs:
The Pierces “You’ll Be Mine”
Sea Wolf “O Maria”
Cursive “Driftwood: a Fairytale”
They all evoke fairytale imagery. What other songs do? Meant for adults, that is, not off of Disney movie soundtracks.
Mother Goose and The Story Of The Hare Who Lost His Spectacles by Jethro Tull.
Gingerbread man - Kickapoo Creek
Christabel - Robert Earl Keen
This song right here will take you far, far away.
“Like Their Feet Had Wings” by Three Weird Sisters
And, of course, the score of Stephen Sondheim’s Into the Woods.
“Little Red Riding Hood” by Sam the Sham and the Pharoahs
Rush - Madrigal, By-Tor and the Snow Dogs, Rivendell, The Fountains of Lamneth, The Necromancer, ah, hell - just borrow all their albums and rummage around…
Alan Parsons Project has an album of Poe Tales of Mystery and Imagination, Dream Within a Dream is very good. He was involved in the soundtrack for LadyHawke.
Rick Wakeman of Yes had a few independent albums, I think Myths and Legends of King Arthur would work for you. I think all of the music is on youtube.
Renaissance, Rainbow and a few other bands have stuff along these lines as well, even Led Zeppelin does, and Tyr is heavy metal with a ragnarok bent.
Many bands in 1968- about 1974ish frequently did unusual things with music, and there was a fashion for fantasy perhaps because of the popularity of Tolkein and the renaissance of F&SF type pulp magazines.
For the ultimate in Tolkien-trippin’ epic metal escapism, look no further than Austria’s Summoning. This song, or else this one. Middle Earth, man - can you see it appearing before your very eyes or what?
For more or less the same but with cleaner, less harsh-sounding vocals, and, uh, with vikings instead of hobbits, this song right here is what you want. Viking metal-era Bathory, with an acoustic intro, clean-ish vocals and all the rest of it. (Don’t watch the video though, it’s too ridiculous for words.)
“Are You Sitting Comfortably” by the Moody Blues might qualify, though it’s more Arthurian than Fairytale-ish.
“A Trick Of The Tail” by Genesis.
That Pierces song always reminds me of vintage Fleetwood Mac.
Although for real fairy Tale music, you wantFaun (although Egilsaga specifically is pagan, not fairy)
There’s always Mediaeval Baebes. (Or Corvus Corax if you want to be …Unseelie)
Renaissance’s gorgeous Ocean Gypsy, or the weirdly wonderful Witches Hat, by the Incredible String Band.
Harry Chapin comes pretty close in TAXI.
“It was somewhere in a fairy tale,” he says, explaining that “I’ve got something inside me to drive a princess blind; there’s a wild-man wizard, he’s hiding in me,” in between chatting up his latest passenger with a slightly archaic and stilted manner – “Where you going to, my lady blue? It’s a shame you’ve ruined your gown in the rain” – and wrapping the whole thing up by concluding (in best fable-narrator style) that “it’s strange, how you never know – but we’d both gotten what we’d asked for, such a long, long time ago.”
Storybook Love with Willy Deville, from The Princess Bride.
Emotion in Motion by Ric Ocasek (especially the video.)
Here’s a beautiful song inspired by Shakespeare’s Midsummer Night’s Dream. (the monster will not hurt you)
Here’s Noe Venable’s “Midsummer Night’s Dream”
Here’s another Tolkien song:
Sally Oldfield - Nenya (Songs of the Quendi)
Pretty much Sally’s entire discography, especially the album Water Bearer sounds fairy-taleish. Yes, she is Mike Oldfield’s sister.
Water Bearer
Mirrors
Night of the Hunter’s Moon
Personal trivia: I discovered Kate Bush, Sally Oldfield and Lene Lovich on the same day. Changed my whole life.
Magician’s Hat - Bo Hansson