松内です。
僕も数十万行～百万行超のLogファイルを扱うのですが、同じ経験があります。
改行文字の置換が原因と言うよりは、正規表現を使ってれば必ず起こっていると思います。
例えば
1
2
3
4
5
6
7
8
9
（空行）
として、それのコピー＆ペーストを繰り返して70万行のファイルを作ってmanhakuさんの再現をしてみたのですが、全体の３％処理するのに5分あまりかかりました（他のソフトも動いていたので、そんなに正確じゃないかも知れませんが）。
CPU使用率が100％になって、他の事が出来ないので、もうそれで止めてしまいました。
同じ物をSpeeeeed
http://akky.cjb.net/download/speeeeed.html
を使って置換してみると一瞬（1秒かからない）で出来るので、こうした巨大ファイルの正規表現置換に関してはこのツールをいつも使っています。
EmEditorで巨大なファイルを扱えるようになった事で、かえってこうした問題が発生しちゃったんでしょうか :-)
OSはWindows2000SP4
CPUはPentium4：2.4GHz
RAMは1GB（512MBのデュアルチャンネル）
です。