OK - it seems an acceptable path forward has been identified. For the interested reader, here's what I learned:
* The PIC18F8520 was originally used because it was upwardly compatible with code developed on previous PIC16x hardware.
* The PIC18F8720 is the "big brother" to the '8520, although (seemingly - the specs on Microchip's site are a little contradictory) limited to 25MHz operation (instead of 40 MHz).
* The PIC18F8722 is Microchips suggested replacement for the PIC18F8720, adding a few more peripherals and 40 MHz (10 MIPs) speed back again.
* The PIC18F87K22 is the upgrade from the PIC18F8722 (!). Page 543 of the datasheet DS39960D details the differences and alludes to the (potential) code changes required.
So... the condensed version is:
the PIC18F8520 *should* be able to be upgraded to a PIC18F87K22, with a core CPU speed increase of 60% (from 10 MIPs to 16 MIPs) ...and hopefully only *minor* code changes required - peripheral clock related headaches as foretold by horace1 notwithstanding
64 MHz (= 16 MIPs due to the CPUclk = Fosc/4) is the highest clock speed available in Microchip's 8-bit family. My reference to 80 MHz in my first post was a misguided consequence of hanging around the PIC32's for too long.
Finally, for the masochistic, I found numerous Google references to open source PIC18 emulators, but it'd take a FAST emulating CPU and a burning desire to really want to bury yourself deep into the architectural subtleties for that to be a viable option. 16 MIPs looks like the practical end of the line