Take a look at this charthttp://www.tomshardware.com/charts/cpu-charts-2013/-34-Adobe-Premiere-Pro-CS6,3171.html
Video encoding is a hell of a lot harder than you give it credit for, especially when encoding to that resolution, the amount of data in play is massive. As you can see on the chart i linked above they were encoding a 2:21 video, the fastest time was an i7 4960X at 166 seconds for 141 seconds of video, thats about 1.18 seconds per second of rendered video at 720P. Since you are trying to encode at a higher resolution its going to take longer, your 15:51 example is about 1.32 seconds per second of final video which is about on par.
Video encoding is hard, this is why people who do it professionally use dual and quad CPU workstations with 64GB of ram and GPU acceleration.