Well, assuming you have the same WHDLoad version of Lemmings as I do, it has a preload size of 1,996,153. I'd throw three options out there:
1 - Try tinkering with the
preload settings2 - Try to reduce memory usage of your Workbench prior to running the game (unload apps/commodities, drop it down to a 2-color screen, etc.)
3 - Add a little more memory
WHDLoad games have a higher memory requirement than just the game itself (since it's loading the game on top of the operating system). Try some smaller games and see how those work for you?