乗算に関しては、Karatsuba法では半分の桁の掛け算を、4つではなく3つに減らすことができるので、「両方の桁数の積」より速く計算することができます（n桁×n桁の掛け算ででO(n^1.59)程度）し、3つの乗算のうち2つは並列実行できます。さらに桁数が増えれば、高速フーリエ変換を使ったアルゴリズムがあって、O(n log n)より少し大きいぐらいのオーダーで処理できます。

これに対して、除算の場合、「分けて計算する」という方法が使えないので、O(n^2)のオーダーから減らすことができません（「割る数の桁数に比例した処理」を「割られる数の桁数に比例した回数」だけ繰り返すことになります）。上の桁が決まらないと下の桁の計算に入れないので、並列実行にも向きません。

結論：除算が遅い、というより、乗算が高速化できるから相対的に遅くなってしまう

なお、「素因数分解で割る数を小さくする」というアイデアは、素因数分解の手間自体が莫大となるため、一般の数に対する割り算の高速化にはほぼ使えません（「素因数分解がおいそれとできない」ことそのものがRSA暗号の安全性の鍵となっている、というように、本質的に困難な問題です）。

もしかして極端に時間がかかる、とは、現代暗号である公開鍵暗号方式の基本となる、RSA 暗号における素因数分解の困難さにまつわる話でしょうか？

割り算が遅いのではなく、素因数分解に近道がない（解くための公式がないため、愚直に試すしかない）ことを示すものです。

※この「近道がない」ことはまだ数学的には証明されておらず、「P≠NP予想」という数学における未解決問題の一つとなっています。

C言語で割り算の桁が増えないように、割り算を複数回に分解して計算したら、速度は向上しますか？？  
桁を減らし、回数を増やした方がはやくなるかな？と思いました。

除算を高速化する工夫ということであればもっと効率的なものがあります。
整数の除算は、1回の乗算に変換することができるのです。
http://www.emit.jp/prog/prog_div.html
もちろん、その変換作業に除算が必要なのですが。

ということは、Cのプログラム上で除数が定数であれば、コンパイルの時点でこの乗算への変換作業をやってしまえば実行時の効率が上がります。
そして、ここまで言えば気付かれていることかもしれませんが、コンパイラにはまず間違いなくこの最適化が実装済みです。

C言語で割り算の桁が増えないように、割り算を複数回に分解して計算したら、速度は向上しますか？？ 
桁を減らし、回数を増やした方がはやくなるかな？と思いました。

基本実行環境での測定（プロファイル）がいちばんの早道です。
また、下手に人間が最適化を行うよりも、コンパイラに任せるのが吉だと思います。
もちろん、大局的な最適化は人間が行った方が良いでしょうけれど。