The O(n) meidan of median algorithm actually partitions the array so that the elements before it are less than it and after it are greater than it.
When you recurse with the median of medians as pivot, you are partitioning the array so that it looks like
(elements less than the median) - p - (elements greater than the median)
On the correctness, when you first query for k = n/2. You get m1 and m2(m1 > m2). Now you know that there are more than n elements that are less than m1. so elements following it will never be candidates for the median.
Similarly elements before m2. there are more than n elements ahead of them, so they will never be a candidate for the median. So the median must lie somewhere in the second half of the second array and the first half of the first array.
But now when you recurse you should keep in mind that you have n/2 elements of the second array counted for, so you need to find the element that would occupy the n/2th position in the sorted union of the two arrays(second half and first half).
This seems asymptotically optimal since you're always reducing the size of the arrays you are recursing on to half. something like O(n) + O(n/2) + O(n/4) ... = O(n).
For sorted arrays you can do this is O(logn).