The stack overflows due to the recursion in merge-and-count. I tried this approach, and for 100000 items, it came back instantly.
(defn merge_and_count [left right inversions]
(loop [l left r right inv inversions result []]
(cond (and (empty? r) (empty? l)) [result inv]
(empty? r) [(apply conj result l) inv]
(empty? l) [(apply conj result r) inv]
(<= (first l) (first r)) (recur (rest l) r inv (conj result (first l)))
:else (recur l (rest r) (+ inv (count l)) (conj result (first r))))))
You need to replace this code with code from your second approach.