こんなに大量のデータを処理したことがない(せいぜい数千件程度)
ので、はっきりした原因はわかりません。多分、以下の2つの事が考え
られます。
 ・データ量が多いので処理に時間がかかっている。
  (エクセルそのものがフリーズしたのではない)
  例えば、1秒で1000件処理したとしても70秒、1秒100件の場合だと
  700秒(約12分)かかることになります。
 ・メモリ不足
  エクセルが作業にどの程度のメモリを消費しているのか分かりません
  が、内部メモリに空きがなくなるとハードディスクをメモリ代わり
  にしますので極端にスピードが遅くなります。場合によってはフリーズ
  するかもしれません。
どちらにしろ、データをいくつかのシートに分割してシートごとに別々に
処理した方がいいと思います。
ハードにも関係してくるので、エクセルの作業だけで解決はできないと
思います。