The ATmega UART hardware certainly supports it.
See section 22 of the '2560 data sheet:
Supports Serial Frames with 5, 6, 7, 8, or 9 Data Bits and 1 or 2 Stop Bits
Odd or Even Parity Generation and Parity Check Supported by Hardware
There's some example C code in the data sheet as well.