You can actually put
Serial.begin(1000000); // 1Bps
it should even work with 2000000. 
I did not test 2Mb with the Hardware serial library but with my own library as I need the serial in half-duplex mode and need some special stuff.
Anyway, you can squeeze a whooping 2Mbps out of an Arduino (tested only on Mega, but should be the same on the others as long as the clock is 16MHz). To modify the UARTnA register bit for Double Speed mode:
bitSet(UCSR0A, U2X0); // NB if you put now speed 10000 it is actually 20000, the UART divider is now 8 and not anymore 16
I am using this on the Arduino Megas TX3, so it is:
bitSet(UCSR3A, U2X3);
I needed that because I bricked ( :o ) a AX-12+ servo setting it to 2Mbit/sec