This RGB matrix project here
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1238559959/15
concludes that the time spent in ISR (to display (shiftOut) the video memory, I would guess) is 50%. And this is only 1 RGB LED matrix (4 x 595s).
You would also have to spend some time doing heavy bit shifting (for scrolling).
Another aspect is the "video memory": 8192 LEDs means at least 8192 bits, that is 1KB (out of 2).