A me sembra strano che sia colpa di json_encode...visto che lo chiami su una singola riga.
Hai provato ad usare mysql_unbuffered_query() invece di mysql_query() ?

Cmq una soluzione può essere quella di paginare i rusultati, invece di prenderli tutti insieme.

Oppure puoi fare un ciclo di $.getJSON, prendendo prima le prime 5000 righe, poi le successive 5000, etc. alla fine unisci tutto (sempre lato client)