Time complexity to find Median of Medians
The running time of counting sort isn't $O(n)$, in general.  If you are guaranteed that every element of the array is an integer in the range $1..n$, then the running time of counting sort is $O(n)$; but if you aren't guaranteed that, in general the running time could be much worse.

Since the question doesn't make any guarantees that the elements of the array will be in a specified range, you can't claim that counting sort will have $O(n)$ running time, and your analysis of Approach #1 is not correct.

Approach #2 does indeed provide an algorithm with running time $O(n^2 \log n)$.  However, that's not the best algorithm.  There are better algorithms, which can find the median in $O(n)$ time.  So, the correct answer is $O(n^2)$ ... but not for any of the reasons listed in your question.  See https://en.wikipedia.org/wiki/Selection_algorithm and Find median of unsorted array in $O(n)$ time.