>There's no doubt he did this, but ... do songs count as literature?

They should. Literature and poetry started from rhapsodies, sagas, and other forms of song-based storytelling, and it's not very good that it diverted so much to some kind of literary ivory tower.