Well technically, the UART is capable of up to 8Mhz in Synhronous Master Mode.
I've had the UART set to run at 8Mhz and outputting video data smoothly in Master SPI mode. I believe the max rate in UART Synchronous master mode is 8Mhz as well. It is double buffered, so actually seems to perform better in some ways than the actual SPI hardware. This would put the maximum transfer rate at 8mHz/8bytes = 1MB/s minus overhead (start, stop bytes etc) So 1MB/s or 8Mbps would be the max rate minus overhead. In non-synchronous modes, the limit is 2mbps according to the datasheet (250KB/s minus overhead).
An example sketch for outputting NTSC video at 8mhz is a bit messy but is here: GitHub - TMRh20/Sketches: Arduino Audio Streaming Realtime, NTSC Video
I did a bit of a writeup on ensuring the output is timed correctly and smooth, which can be found at my blog:
It may not work that well at 8mhz for actual communication, I haven't tested that specifically. It might require a kind of custom solution as well, as the Arduinos would not be able to stream at 8MHZ continuously without a large memory buffer.
*Edit to add: Just remembered, that I have used it at 8mhz in SPI mode for controlling a radio module and it worked well for that communication, so there is no reason it wouldn't work otherwise.