Software serial can run at 115200, but only if no other interrupts are happening. Sending serial data through the hardware serial port causes interrupts that interfere with software serial, causing data loss at high baud rates.
As tuxduino suggests, lower the software serial baud rate or minimize what you are printing to the hardware port. Or both.