I could have sworn I saw a documentary where they talked about having legal issues with some of the music, because some of it (e.g. "She'll Be Coming Round the Mountains") was not public domain.

There's a little bit written about it on Wikipedia but I wish I could find the documentary: https://en.wikipedia.org/wiki/Lemmings_(video_game)#Developm...