The reason behind the discrepancy in documentation is that the documentation refers to two different versions of the software and it is out of date.
In Arduino version 0023 and below, SoftSerial was a very basic library written by David Mellis. It just uses millis(), digitalRead/Write and blocks when sending or receiving. This means it can work on any pin. However, it works badly and slowly. I would strongly recommend avoiding this.
In Arduino version 1 and above, SoftSerial was replaced with NewSoftSerial. This uses interrupts and timers, and is far more efficient. This limits the pins that it can work on though to ones that have pin change interrupts.
With respect to the contradictory pins; there are two types of interrupt pin on the ATmega2560 - external interrupts (INT7 - INT0) and pin change interrupts (PCINT23 - PCINT0). External interrupts are more complex and can be configured to trigger on rising and/or falling edges. Pin change interrupts trigger as long as any change occurs.
The long list of:
10, 11, 12, 13, 50, 51, 52, 53, 62, 63, 64, 65, 66, 67, 68, 69
are pin change interrupts which are what are required for NewSoftSerial (called SoftSerial in Arduino 1.0 and above).
The short list of:
2 (interrupt 0), 3 (interrupt 1), 18 (interrupt 5), 19 (interrupt 4), 20 (interrupt 3), and 21 (interrupt 2).
are external interrupts.
You can see these on the pin mapping diagram for the ATmega2560 (which is correct, AFAIK). Function of the interrupt pins is described on page 105 onwards of the datasheet.
There are 4 hardware USARTs on the ATmega2560. These are far easier to use and far more efficient than any software serial library. They are on pins 0/1, 14/15, 16/17, 18/19.
There is also AltSoftSerial which is better than NewSoftSerial in terms of performance, but is even more limited in pin choice.
At this stage, I have to ask "why those pins?". Could the design not change?