Bizarre compilation problem -- only compiles with the addition of a single Serial.println() line?
Update: This seems to be a linker bug. Quick fix: upgrade your
Arduino installation. See the end of this answer for details. What
follows is the first version of this answer, with a detailed explanation
of the error message.



You have a problem linking the interrupt vector table with your program.
I quite understand what the error message means, but I do not understand
how in the world you can possibly have this error. This should not
happen. I will try to explain the error anyway.

The Arduino Mega is based on an AVR chip. The AVR instruction set has
“jump” and “call” instruction that come in two flavors:


“absolute” jumps and calls (opcodes: jmp and call) can address the
whole flash memory, which means you can branch from any part of the
program to any other part, without restrictions.
“relative” (a.k.a. “PC-relative”) jumps and calls (opcodes: rjmp and
rcall) have limited range: they can only bring you to nearby places,
no more than 4&nbsp;K from your starting point.


The relative flavors take less space and execute faster, they are thus
better if the destination is close enough. On the smaller AVR chips
(up to 8&nbsp;K of flash), they can access the whole flash, then these
chips lack the absolute flavors.

How the vector table is normally linked

Every program you build for an AVR starts with an “interrupt vector
table”. This is a series of jump instructions that are automatically
executed whenever an interrupt triggers: if the n-th supported
interrupt triggers, then the hardware automatically loads and executes
the n-th jump instruction, which will jump the execution of the
program to the corresponding ISR (interrupt service routine). The
table is chip-specific: on the smaller AVRs (up to 8&nbsp;K), it's a
table of rjmp, whereas on the bigger ones it's a table of jmp. This
table is part of the CRT (C run time) provided by the avr-libc library
in a file named crtXXX.o, where XXX is a code identifying the chip. The
Arduino Mega being based on the ATmega2560 chip, it's CRT is crtm2560.o.

I disassembled my own copy of crtm2560.o and found this vector table:

00000000 &lt;__vectors&gt;:
   0:   0c 94 00 00     jmp 0
   4:   0c 94 00 00     jmp 0
   8:   0c 94 00 00     jmp 0
   ...
  e0:   0c 94 00 00     jmp 0


You can see these are all jmp instructions (absolute flavor), as
expected for any AVR with more than 8&nbsp;K of flash. The address of
the jump, however, is always 0, which is obviously wrong. This is
because the proper addresses cannot be known until the program is fully
built. When you build your program, the linker will put all the pieces
together. It will then know where the ISRs are, and it will patch the
vector table to make it correct. This kind of patching is known as
“relocation”, and the linker performs this based on some “relocation
records” included in the CRT. Here are the relevant records from my copy
of crtm2560.o:

RELOCATION RECORDS FOR [.vectors]:
OFFSET   TYPE              VALUE 
00000000 R_AVR_CALL        __init
00000004 R_AVR_CALL        __vector_1
00000008 R_AVR_CALL        __vector_2
...
00000090 R_AVR_CALL        __vector_36  [*]
...
000000e0 R_AVR_CALL        __vector_56


The record I marked with [*] means: “at offset 0x90 into the vector
table there is an absolute jump or call instruction, and the instruction
should be modified to point to __vector_36”. This tells the linker
how to fix the table when building the program.

If I instead disassemble a CRT for a smaller chip, I get a smaller table
made of rjmp (instead of jmp) instructions, and the relocation
records look like this:

RELOCATION RECORDS FOR [.vectors]:
OFFSET   TYPE              VALUE 
00000000 R_AVR_13_PCREL    __init
00000002 R_AVR_13_PCREL    __vector_1
00000004 R_AVR_13_PCREL    __vector_2
...
00000032 R_AVR_13_PCREL    __vector_25


These records mean “at offset XXX into the vector table there is a
PC-relative jump or call instruction, and the instruction should be
modified to point to __vector_XXX”.

Your error message

Your error message provides the following information:


“crtm2560.o”: this is your CRT, where the vector table and the
relocation records live.
“.vectors+0x90”: this means the problem is at offset 0x90 into the
vector table.
“R_AVR_13_PCREL against symbol `__vector_36'”: this means there
is a relocation record of type R_AVR_13_PCREL (PC-relative jump or
call) referencing __vector_36. Here seems to be the problem.
“defined in [...] core.a(HardwareSerial.cpp.o)”: this __vector_36
is part of the serial port code from the Arduino core library.
“relocation truncated to fit”: __vector_36 is too far to be reached
by a PC-relative jump, thus the linker could not relocate properly.


The problem seems to be that the relocation record is of type
R_AVR_13_PCREL, which is what you expect on smaller chips but not on
your ATmega2560. You normally expect R_AVR_CALL.

Now, about the strange behavior: the exact point where the ISR lands
when the program is built is difficult to predict. Add or remove a few
lines in your code and the linker may bring the pieces together in a
different order. Then, the infamous __vector_36 may end up being in
range or out of range of a relative jump. Given the nature of the error,
the behavior you find “strange” is actually quite normal.

Further debugging

The root of the problem seems to be an incorrect relocation record in
your CRT. You can try to disassemble the CRT to see what is wrong:
search your computer for a file named crtm2560.o, probably in
/Applications/Arduino/Arduino.app/Contents/Resources/Java/hardware/tools/avr/avr/lib/avr6
or a similar place. The tool needed for disassembling is called
“avr-objdump” and should be hidden somewhere in your Arduino
installation folder. Once you find the files, start a terminal and type

/path/to/avr-objdump -d /path/to/crtm2560.o


with “/path/to” replaced by the actual paths. You should see something
very much like the first listing of my answer, with lots of jmp
instructions. If you have rjmp instructions instead, then something is
already wrong at this level.

To see the relocation records, type:

/path/to/avr-objdump -r /path/to/crtm2560.o


The output should look like my second listing, with lots of R_AVR_CALL
records. If you have R_AVR_13_PCREL instead, the records are wrong.

If this is the problem, then the obvious fix would be to replace the
broken CRT with a sane one. You may try to reinstall the whole Arduino
package. If you still have a corrupted CRT, you should report the error
to the Arduino folks. Then you may try to fetch a fresh copy of the
avr-libc and replace the relevant
parts of your Arduino installation. Replacing just the CRT may or may
not work: I don't know whether the last version of the CRT has
incompatibilities with older versions of the rest of the libc.

Update: this is a linker bug

I did some research, and I now believe you have hit a linker bug. There
is a gcc option called -mrelax that allows some link-time
optimizations. One if them is to have the linker replace some absolute
jumps and calls by the smaller and faster relative ones. Obviously, this
is only possible if the target address is within reach of the relative
jumps or calls. There was a bug in old versions of the GNU linker (up to
2.22) where, under some obscure circumstances, it would erroneously
believe the target was reachable, only to find out later that it was
not. This bug mainly affected the interrupt vector table, producing the
kind of error message you are seeing now.

Here is a partial timeline of this bug and its fix:


November 2011: this is filed as
bug 13410
on the bug tracker for the GNU binutils package.
January 2012: Vidya Praveen, from Atmel, publishes a fix.
February 2012: the fix is committed to the development version of
binutils.
October 2012: GNU binutils 2.23 is released, including the fix.
The same month, the bug is reported again as
issue 1071
on the Arduino issue tracker.
June 2013: Paul Stoffregen links this new issue to the old bug.
June 2014: Arduino gets an updated
toolchain
including binutils 2.23.2, which fixes the bug in the development
version of Arduino.
July 2014: Arduino 1.5.7 beta is
released including the
updated toolchain.
September 2014: Arduino 1.0.6 is released with the old toolchain.


A workaround for the bug has been
published by Mark Anderson on stackoverflow. The real fix, however,
would be to upgrade to the latest Arduino package (1.6.1 as of this
writing).