Why doesn't the duration of a Premiere Pro encoding scale linearly?
I doubt it is memory or page fault related.  Encoding is more of a stream operation, you load a frame, process the frame, hold the frame until you finish a group of pictures and then encode the group of pictures.  It is not a memory intensive process unless you are doing fancy effects that require memory to process.  It is a potentially HDD stream intensive process as it has to stream the video sources off the HDD and then record the output back to the HDD, which could involve lots of seeks potentially to move between reading and writing.

The two things I would try would be to try CUDA acceleration first and see if you can offload the processing to your GPU.  If that doesn't get sufficient speed I would try making sure your system is defraged and if that doesn't give sufficient speed, I might try SSDs for processing to and from for better random access of assets.

It is also possible that it is simply harder to encode later parts of your video though.  Depending on the exact settings you are using, changes in the content of the video can make a significant impact on how difficult it is to encode the video, so it may not even be unexpected that the encoding time changes between the first minute and the rest of the video.