And just to be clear, most examples posted here are not Doom-clones, but Wolf3d-routines. There actually is a big difference.
Anyway, I made a wolf3d-routine on a stock A500 that runs in 80x90 resolution with 12bit colors (in copperchunky). It runs at 25fps, so adding enemies and game logic would most certainly slow it down even more. But considering a lot of people seem to think something running at 10-15fps is playable, it shouldn't be a problem