Electronic – Software interrupt vs function

You'll find the information you need in the compiler's manual: MPLAB C18 C COMPILER USER'S GUIDE.

From page 37 of the user's guide:

MPLAB C18 does not automatically place an ISR at the interrupt vector. Commonly, a GOTO instruction is placed at the interrupt vector for transferring control to the ISR proper. For example:

void lowPriorityISR(void);

#pragma code low_vector=0x18
void interrupt_at_low_vector(void) { 
    _asm GOTO lowPriorityISR _endasm 
}
#pragma code

#pragma interruptlow lowPriorityISR
void lowPriorityISR() {
}

When implementing a high priority ISR, you cannot use the interrupthigh pragma as you would expect. You'll have to use the interrupt pragma instead, as is described here.

If you can change the compiler: using interrupts is easier in the Microchip XC8 or HI-TECH PICC compilers.

As you've discovered, handling counter overflow with an interrupt handler is tricky and race-prone. Even with your priority boost, you'll get the wrong answer if interrupts are disabled while you read the counter. There's a much simpler technique which works if you're not reading the clock from interrupt context (note that I'm using the DWT cycle counter here, which is built into the processor thus fast and simple):

uint64_t last_cycle_count_64 = 0;

// Call at least every 2^32 cycles (every 59.6 seconds @ 72 MHz).
// Do not call from interrupt context!
uint64_t GetCycleCount64() {
  last_cycle_count_64 += DWT->CYCCNT - (uint32_t)(last_cycle_count_64);
  return last_cycle_count_64;
}

If you need to call it from interrupt context (or with a preemptive OS):

volatile uint64_t last_cycle_count_64 = 0;

// Call at least every 2^32 cycles (every 59.6 seconds @ 72 MHz).
uint64_t GetCycleCount64() {
  uint32_t primask;
  asm volatile ("mrs %0, PRIMASK" : "=r"(primask));
  asm volatile ("cpsid i");  // Disable interrupts.
  int64_t r = last_cycle_count_64;
  r += DWT->CYCCNT - (uint32_t)(r);
  last_cycle_count_64 = r;
  asm volatile ("msr PRIMASK, %0" : : "r"(primask));  // Restore interrupts.
  return r;
}

You may need to enable the cycle counter first:

DWT->CYCCNT |= DWT_CTRL_CYCCNTENA_Msk;  // Set bit 0.