I think you will have to break it up. But why are needing update so many? Once you issue an invoice you should not need to modify it. It is also illegal in many countries to modify invoices after they are issued.
Divide it in batch of 500 or 1000.
Also try to delete irrelevant columns which you are not updating.
In your case Division column for each line and key column would be needed.