I came across this old Amiga demo,
Puggs in Space... if you watch that into the main part, the music sounds like the TIM3 song from the original Lemmings game. However, I looked this demo up and it was released in 1989. And this is more than just a passing resemblance. It's nearly exact.
Huh. Strange it would be used in Lemmings though, seeing as all the other songs were classical music or popular public domain tunes.