How fast ist client.wirte() on MEGA

I think you are limited to 4MHz on the SPI bus with the w5100. However, sending an array of characters is much more efficient that one character per packet. The overhead becomes a real speed problem.

// this takes 6 packets
client.print('h');
client.print('e');
client.print('l');
client.print('l');
client.print('o');
client.println();

// this takes one packet
client.println("hello");

The w5100 4MHz SPI speed should handily outrun the serial port's 115200.