Haven't you done the math yet?
115200 baud = 115200 bits per second
= 11520 bytes per second
= 11.5 bytes per millisecond
You can't send that many characters in the 1 mS time frame, it has nothing to do with the "processing power" of the Arduino, but the baud rate.