Given that the original game predated those sorts of systems hitting consumer desktops by years, it shouldn't be surprising at all. This is what early 3d games & software rendering did before accelerators came along, and as CPUs got faster in that interim there were plenty of fully polygonal software rendered engines as well.
I wonder how many polygons make up a level of Wolfenstein in total - i.e. if you just asked a modern GPU to render every single wall in a level and relied on it to do the z-order sorting, culling, etc., what frame rate would you get?
I'd guess that if you were to triangulate an average map it might have probably been only in the region of 1-10k triangles.
Modern graphics cards on the other hand can easily push a few million triangles every frame with decent framerates. At 10k triangles * 10 or 20 maps you could load all maps from the game simultaneously and still easily get decent fps.
