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.

Interesting how meaning changes. Back when Wolfenstein was made, "without a graphics API" just meant

    mov ax, 13h
    int 10h

... and even there you were using a graphics api, provided by your video card's bios and compatible across various manufacturers.

Not really - you'd be mostly just writing into the video buffer.

int10h is the API (BIOS)... that just causes the mode switch. What he really meant (direct RAM access):

   void putpixel_13h(int x, int y, int color)
   {
      _farpokeb(_dos_ds, 0xA0000+y*320+x, color);
   }

Yeah, but nobody does that.

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.