AVR Measuring frequency using external interrupt - where are my cycles going?
As @angelatlarge said your first task is to view the disassembly of your interrupt vector to determine how many cycles your code actually takes.  Second, you have to realize that there is  additional overhead associated with a call to an interrupt vector.  Here is an extract from the ATMega328P datasheet, section 7.7.1 - this should be representative of all AVRs:


  The interrupt execution response for all the enabled AVR interrupts is four clock cycles minimum. After four clock
  cycles the program vector address for the actual interrupt handling routine is executed. During this four clock cycle
  period, the Program Counter is pushed onto the Stack. The vector is normally a jump to the interrupt routine, and
  this jump takes three clock cycles. If aninterrupt occurs during execution of a multi-cycle instruction,this instruction
  is completed before the interrupt is served. If an interrupt occurs when the MCU is in sleep mode, the interrupt exe-cution response time is increased by four clock cycles. This increase comes in addition to the start-up time from the
  selected sleep mode.
  A return from an interrupt handling routine takes four clock cycles. During these four clock cycles, the Program
  Counter (two bytes) is popped back from the Stack, the Stack Pointer is incremented by two, and the I-bit in SREG
  is set.


So, to sum it up:


4 clock cycles to push PC onto the stack
3 clock cycles to jump to interrupt handler
Up to 3 clock cycles if a multi-cycle instruction is interrupted (AVR instruction set table in the same document indicates that 4 cycles is the longest instruction)
4 more clock cycles when exiting the interrupt to restore PC, increment SP, etc.


This adds anywhere from 11-14 additional cycles of overhead on top of however many cycles your interrupt code takes.