Check your PCON register setting (see the PIC16F62xA datasheet, section 14.2.8).
You might actually be running at 37khz vs. 4mhz if you are using the internal clock.
By my calculations, it should actually be starting up about 16 seconds after power on if you haven't defined any other oscillator setting (meaning the default setting of 4mhz is used by default). It makes more sense if you've actually 'defined' 8mhz.

Does the whole program run slow or just the start up?

JDG