Witch Queen Of New Orleans - Redbone
j
ETA: strictly supernatural rather than magical:
B.o.B. - Magic
No one has mentioned “Could it be magic?” by Barry Manilow. Don’t throw things at me, it’s his only song that I like.
I’m only kicking myself for forgetting it.
Magic Bus - The Who
Already on the playlist.