Arduino encoder with CAN BUS

To me it appears you have run out of bandwidth (not fast enough) with your mega. Have you tried using one of the many timers as a counter, it will accumulate the counts in hardware and reduce your interrupt load dramatically.