I did some progress on the SNES version tonight (and redid level 2 and 3), now it beats the first 6 levels in 4:47:
http://acmlm.cjb.net:2/Emu/snes/Snes9x/smv1/Lemmings-2.smv
1: Might be a little faster if I used the Digger a little later, to minimize the digging to do, but otherwise optimal
2: Used the Floater at the last possible moment, killed off the rest, should be optimal
3: Now optimizing it starts to get a little tricky ... the default release rate wastes time, and 99 all the way gives too many unneeded lemmings to nuke (causing lag), so I have to find the best changes to do. The rest is easy (and you'll notice they survive the higher drop at the bottom, unlike on NES)
4: Again, I had to find the best release rate variations to avoid lemmings walking back and forth (getting behind the rest) more than they should
5: Full 99 here ... but then I had to handle a whole crowd of lemmings so none would turn back, which fortunately was possible
6: No blockers, perfect timing, and some more release rate fun
Even the simple levels at the start require some planning and take a while to do, doing level 2 to 6 took hours and over 1000 re-records, this could be a very long run to make.
I also did things with the cursor instead of only playing music, and I should probably find entertaining ways to kill unneded lemmings (without wasting time) in the later levels ...
The NES version isn't as good, but things move faster, levels are shorter, there's less lemmings and no need to worry about finding the optimal release rate, so it'd be easier to do.
(edited)
Just heard about Select+Start ending the level without having to nuke ... this could save much more time.