Merge sort worst case running time for lexicographical sorting?
The recurrence formula is incorrect. 

Lets say you have $t$ strings, so the running time of merge isn't $O(t^2)$ but $O(t\cdot n)$.

Change variables: the input size is $m=n^2$, and the recurrence formula should be

$$T(m)=2 T\left( m/2 \right) + O(m) $$ 

So you get $T(m)=O(m\log(m))$ and therefore $T(n^2)=O(n^2\log(n))$.