Excel unterstützt ja erst ab Office2007 1Mio Zeilen, vorher sind's max. 65535 Zeilen.
Man muss dann wohl je 65535 Zeilen ein neues Blatt erstellen, wobei nur max. 255 Blätter unterstützt werden.

Ansonsten wirst du die Excel-Dateien mit Excel selber nie bearbeiten können.

Könnte wohl eher das Problem sein, dass ein Java-Programm in 32-Bit nur 4GB Speicher haben kann, was bei dieser Anzahl Sätzen ja durchaus nicht ausreichen kann.