Well, I'm not sure exactly what the songs are.
I know Vitamin C - "Friends Forever" (or maybe a song that really sounds like it) is in there, one track is from Barenaked Ladies (level 12 I believe), a couple are Spice Girls (those should be very recognizable =P), and two others that I have no doubts about (okay, that was horrible) are "Don't Speak" by No Doubt (level 13) and "Runaway Train" by Soul Asylum (don't remember what level number, but it's definitely in there).
I know that in the sequel game (Cheapo Copycat Lemmings Game, we usually just refer to it as "Cheapo" around here), you can extract the midis by, while they're playing, use the Windows key to switch to another window without closing Cheapo, and in the cheapo folder, there'll be a tempmidi.mid file - which will be whatever song is currently playing. Some of these midis, if you open them in a midi editor, it'll have info on what song it is. (EDIT: This trick works in the level editor, too, not just the main game.)
I also remember hearing - BUT I could very well be wrong on this - that the title screen music is an original composition.
By the way - is your username a reference to Tidus from FFX, by any chance?