Firstly, what version of Arc are you using and next what version of excel?
The old xls had a limit of 65536 rows (2 ^ 16).
xlxs or what ever its called had just over a million rows. ( 2 ^ 20).
Is there some funny headers in the data?
Best place is the table to excel tool, but you say this is erroring out. Check paths for spaces etc.