Možná jsi na limitu či za limitem, co ten tvůj tabulkový procesor zvládne.

Mám také jednu rozsáhlou *xlsm "aplikaci" (používám to jako nástroj pro aktualizaci rozsáhlého překladu jedné hry), desítky tisíc řádků na mnoha listech, makra… a některé třídící či vyhledávací operace (nad desítkami tisíc položkami) také pár desítek vteřin trvají… musím to vydržet :)
Ten *xlsm má "jen" přes 10mega.

Ty sám bys měl posoudit, zda převod do databáze by nemohl být řešením tvého problému.