Was it running on that hardware or an OCS machine with a faster CPU?
It runs full speed on a stock 1200, and I wouldn't be surprised if it ran on a 500 as well.
The thing people are missing about demos is that they are
not games; for example, Superoriginal doesn't have a working game engine with sprites, sprite occlusion, AI, free movement etc and is undoubtedly heavily optimized narrowly for exactly the kind of scene that is displayed, most likely with a lot of memory taxing precalculations. Still very impressive, but far from a game.
... and what people seem to be forgetting about other 3D games for the Amiga is that, in the end, they are
not Wolfenstein 3D. There's really only one way to conclusively prove that an A500 is capable of playing Wolfenstein 3D at an acceptable framerate...