Here is the argument I alluded to in my earliest comment. I claim that a sorted $n\times n$ matrix $A$ can be linearly sorted in $n^2 \log_2 n + O(n^2)$ comparisons. To do this, we maintain a vector $v$ which records up to $n$ values of $A$ in increasing order (and their corresponding locations $i,j$). Initially, take $v$ to be the first row of $A$.
We then iterate the following procedure $n^2$ times: output the least value of $v$, delete it from $v$, and insert into $v$ the entry directly underneath it in $A$ (if there is one). Since $v$ is sorted, finding the lowest value takes $0$ comparisons, but insertion of the new value requires a binary search on $v$, which is $\lceil \log_2 m \rceil \le \log_2 m + 1$ comparisons, where $m \le n$ is the length of $v$.
It should be clear that we never insert any value into $v$ before exhausting all smaller values, so if we iterate $n^2$ times this gives a linearly sorted list. The number of comparisons is at most $n^2 (\log_2 n + 1) = n^2 \log_2 n + O(n^2)$, proving the claim.
However, to sort an arbitrary matrix of $n^2$ elements requires at least $\log_2(n^2!)$ comparisons in the worst case, and this is equal to $n^2 \log_2 n^2 - O(n^2) = 2n^2 \log_2 n - O(n^2)$ . Therefore, getting from an arbitrary matrix to a sorted matrix must consume at least the difference of these two amounts of comparisons in the worst case, namely $n^2 \log_2 n - O(n^2)$.