Bottom up merge sort in Haskell
You've spotted the problem. Your merge function is flawed.  For each pair it processes, it introduces an extra unnecessary call to merge.  That is, for a list like [1,2,3,4,5,6], instead of your first merge call expanding directly to:

merge [[1],[2],[3],[4],[5],[6]]
= merge $ mpair [1] [2] : mpair [3] [4] : mpair [5] [6] : []


it expands to:

merge [[1],[2],[3],[4],[5],[6]]
= merge $ mpair [1] [2] : merge $ mpair [3] [4] 
  : merge $ mpair [5] [6] : merge []


As a result, your count of merge calls is O(n) and your count of mpair calls is O(n^2) (or similar -- I didn't check exactly). when they should be O(log n) and O(n log n) respectively.

Instead, you want to split merge up into two functions:

merge :: Ord a =&gt; [[a]] -&gt; [[a]]
merge [] = []
merge [x] = [x]
merge ls = merge (mergePairs ls)

mergePairs :: Ord a =&gt; [[a]] -&gt; [[a]]
mergePairs (l1:l2:ls) = mpair l1 l2 : mergePairs ls
mergePairs ls = ls


This will speed up the algorithm enormously, and it will now run on tens of millions of integers.