Micro controller clock speed requirement for delay measurement
If I were designing this circuit myself, I'd aim for 40MHz, or 40MHz-ish. (Well actually if I were designing this circuit myself I'd find a CPLD or some small discrete logic to handle the high-speed timer part, but this question is how to best apply a microcontroller to the problem.) The reasoning goes as follows:


  I highly doubt an MCU with a core speed of 20Mhz will suffice, since the code to answer interrupts and hold a count will consist of more than one instruction.


That's actually not a concern. As long as the interrupt latency is constant then it falls right out of the equation, i.e. your first timer capture would be TC1 = T1 + Tlatency, your second capture would be TC2 = T2 + Tlatency, so your time difference you are calculating would be TC2 - TC1 = (T2 + Tlatency) - (T1 + Tlatency) = T2 - T1, exactly what you were trying to measure. Or alternately it takes you Tlatency to kick off the clock and Tlatency to stop it, so again it cancels out.

Of course, the above only holds true if Tlatency is nice and constant, so the key is to figure out how much jitter you will have in your interrupt latency. For the time being, I'm assuming the jitter is low (latency is constant). As @crj11 pointed out, if you have hardware capture registers then you can sidestep this whole issue entirely.

As you point out, a 20MHz clock has a 50ns period, but I would presume that the interrupt would have an uncertainty of about 1 clock cycle, since the 1PPS GPS signal is free-running with respect to your microcontroller clock. So the extra factor of 2 in the clock accounts for that.


  I understand that if I want to do anything else with this microcontroller such as send this time delay via UART will consume more clock cycles as well.


Again, not a problem presuming you are using the microcontroller's built-in counter. Whether you are using a hardware capture like @crj11 mentioned, or even if you have an interrupt service routine starting and stopping the timer, you have two really small and fast interrupt events happening every second, and you can spent the rest of the time (in a main loop or a lower-priority interrupt routine) shuffling the data out the UART.