Um...on demand paging works quickers than you think.
You have a page directory that breaks the memory up in to page tables, with each being 4KB big. (You can do 2MB, but normally you stick with 4KB pages.)
Here's why it would be quicker than just using software to do it, the software doesn't have to know anything is why. It just accesses memory as normal, and when it hits a page that isn't in memory, a fault is generated.
The IDT #PF gate is then called and it is responsible for loading the page. So the speed is critical to how that function loads. It can use caching to its advantage, so you don't need to access the hard drive as much.
It works far quicker than you would think.