連動型複合検索フォームのカスタマイズ

カテゴリ量にもよると思います。
10×10程度であれば最初に取得させておいてjsでの表示切替のみで対応してしまいます。
この場合はjavascriptでのoption要素の追加、削除だけですのでajax通信は必要ありません

今どきのPC・スマホであれば50×50でも重くなることはないと思いますが（たぶん）
ソースにずらずらと出るのが嫌なのでそこまでになったら
ajaxでその都度、下位カテゴリを取得します。（本当に個人の好き嫌いの話です）

最初に全部取得するのであれば、取得後に整理する必要がありますがget_terms()を使います。
wp_list_categoriesでもツリー上で取得できるので
置き換えや取得をうまいことカプセル化できればこちらのほうが楽そうではありますが…。

で、私なら2000くらいだとajaxで都度取得という形にしてしまいます。
この辺りは人によって色々な作り方があると思いますのでひとつの方法としてですが
上記と同様にget_termsでparent=>0のものを取得しておいて
jQueryで.on(‘change’)をトリガーに用意したphpにidを送信して
受信したphp側で再びget_termを使い、parentを受信したidで指定した上で
htmlを組み立てて送り返す…という感じになります。
※wafの設定してあるサーバではそのままでは動かないことがあります。