I wish people'd stop using explicit URLs to describe what's REST an what isn't. “Pretty” URLs are incidental, at best.

I'm not certain DELETE is completely inappropriate here[1], but if you feel strongly about it, probably the best/REST way to “delete” a song from a playlist would be to PUT the playlist without the song included.

[1] It is just an ordered list of songs, after all.