Back then almost all UI rendering was software based. The graphics card just needed a large enough frame buffer.
The lack of fancy compositing and animation effects gave these high resolutions devices comparable performance to their standard resolution counterparts.
1600x1200 was commonplace as early as 2001 (in a Dell Inspiron 8000, I believe).
I feel obliged to mention that I have an i8k and it's still working beautifully.
It was a lot easier back when all you cared about was the 2D performance of basic shapes (lines, circles, fills), and the animation for moving a window was just an outline.
Back when there were CRTs, people were regularly running 2048x1536 on Windows 98 era hardware.