Let us denote the arrays by $A_1,\ldots,A_k$, their sizes by $|A_1|,\ldots,|A_k|$, their medians by $m_1,\ldots,m_k$, and their union by $\mathbf{A}$. We will try to solve the following more general problem: given $t$, determine the $t$'th smallest element in $\mathbf{A}$.

Let $m_r = \min(m_1,\ldots,m_k)$ and $m_s = \max(m_1,\ldots,m_k)$. Define $$ N = \sum_{i=1}^k \lceil |A_i|/2 \rceil. $$ There are at least $N$ many elements in $\mathbf{A}$ whose value is at least $m_r$, and at least $N$ many elements in $\mathbf{A}$ whose value is at most $m_s$.

If $N \geq t$ then elements larger than $m_s$ cannot be the $t$'th smallest element. In particular, we can throw out the upper half of $A_s$. Similarly, if $N \geq n+1-t$ then elements smaller than $m_r$ cannot be the $t$'th smallest element, and so we can throw out the lower half of $A_r$ (and update $t$ accordingly, by subtracting $\lfloor |A_r|/2 \rfloor$). Note that $\min(t,n+1-t) \leq \lceil n/2 \rceil \leq N$, and so at least one of these cases must happen.

How many rounds does it take this algorithm to complete? Each round results in reducing the size of one of the $k$ arrays roughly by half (the reduction is $\ell \mapsto \lceil \ell/2 \rceil$). One can check that it takes $\lceil \log \ell \rceil$ steps to reduce each array to a singleton. Therefore the number of rounds it takes the algorithm to narrow down all arrays to a single element is $$ \sum_{i=1}^k \lceil \log |A_i| \rceil \leq k + \sum_{i=1}^k \log |A_i| \leq k + k \log \sqrt[k]{|A_1| \cdots |A_k|} \leq k + k \log \frac{|\mathbf{A}|}{k}. $$ After an initial round which takes $O(k\log k)$ time, each subsequent round can be implemented in $O(\log k)$, if we store the medians in an appropriate data structure such as a heap. Following this phase, we are left with $k$ elements, and we can run a linear time selection algorithm to find the $t$'th smallest element in $O(k)$. In total, this algorithm runs in time $$ O\bigl(k\log k + k \log \tfrac{|\mathbf{A}|}{k}\bigr) = O(k\log |\mathbf{A}|). $$ When $|\mathbf{A}_i|=n$ for all $i$, this is $O(k\log (kn))$.

Let us denote the arrays by $A_1,\ldots,A_k$, their sizes by $|A_1|,\ldots,|A_k|$, their medians by $m_1,\ldots,m_k$, and their union by $\mathbf{A}$. We will try to solve the following more general problem: given $t$, determine the $t$'th smallest element in $\mathbf{A}$.

Let $m_r = \min(m_1,\ldots,m_k)$ and $m_s = \max(m_1,\ldots,m_k)$. Define $$ N = \sum_{i=1}^k \lceil |A_i|/2 \rceil. $$ There are at least $N$ many elements in $\mathbf{A}$ whose value is at least $m_r$, and at least $N$ many elements in $\mathbf{A}$ whose value is at most $m_s$.

If $N \geq t$ then elements larger than $m_s$ cannot be the $t$'th smallest element. In particular, we can throw out the upper half of $A_s$. Similarly, if $N \geq n+1-t$ then elements smaller than $m_r$ cannot be the $t$'th smallest element, and so we can throw out the lower half of $A_r$ (and update $t$ accordingly, by subtracting $\lfloor |A_r|/2 \rfloor$). Note that $\min(t,n+1-t) \leq \lceil n/2 \rceil \leq N$, and so at least one of these cases must happen.

How many rounds does it take this algorithm to complete? Each round results in reducing the size of one of the $k$ arrays roughly by half (the reduction is $\ell \mapsto \lceil \ell/2 \rceil$). One can check that it takes $\lceil \log \ell \rceil$ steps to reduce each array to a singleton. Therefore the number of rounds it takes the algorithm to narrow down all arrays to a single element is $$ \sum_{i=1}^k \lceil \log |A_i| \rceil \leq k + \sum_{i=1}^k \log |A_i| \leq k + k \log \sqrt[k]{|A_1| \cdots |A_k|} \leq k + k \log \frac{|\mathbf{A}|}{k}. $$ After an initial round which takes $O(k\log k)$ time, each subsequent round can be implemented in $O(\log k)$, if we store the medians in an appropriate data structure such as a heap. Following this phase, we are left with $k$ elements, and we can run a linear time selection algorithm to find the $t$'th smallest element in $O(k)$. In total, this algorithm runs in time $$ O\bigl(k\log k + k \log \tfrac{|\mathbf{A}|}{k}\bigr) = O(k\log |\mathbf{A}|). $$ When $|A_i|=n$ for all $i$, this is $O(k\log (kn))$.

Let us denote the arrays by $A_1,\ldots,A_k$, and their union by $\mathbf{A}$. Assume for simplicity that their size is odd, say $2m+1$, and consider the elements in the middle, $m_i = A_i[m+1]$ (the entire array is $A_i[1],\ldots,A_i[2m+1]$). Suppose further that all elements are distinct, and $m_{i_1} < \cdots < m_{i_k}$.

Let $j \in [k]$. Since $m_{i_1} < \cdots < m_{i_j}$, we know that there are at least $j(m+1)$ elements in $\mathbf{A}$ which are at most $m_{i_j}$. If $j(m+1) > k(2m+1)/2 = k(m+1/2)$, then this means that any element larger than $m_{i_j}$ is too large to be the median. This rules out the upper half of $A_{i_k}$. Similarly, we can rule out the lower half of $A_{i_1}$. This enables us to throw out a $1/k$ fraction of all elements at a cost of $O(k)$, which is needed to determine $i_1,i_k$.

After the first round, the median of the trimmed arrays is the same as the median of the original ones, since we removed an equal number of elements from each side of the median. However, now we lose the property of all arrays having the same size. Still, it seems plausible that we can adjust our strategy to take this into account. If it all works out, then we need to perform $\log_{1-1/k} (nk) = O(k \log (nk))$ rounds. While the first round costs $O(k)$, subsequent rounds should cost only $O(1)$, since only two arrays change each round. This will result in a total running time of $O(k\log(nk))$.

Let us denote the arrays by $A_1,\ldots,A_k$, their sizes by $|A_1|,\ldots,|A_k|$, their medians by $m_1,\ldots,m_k$, and their union by $\mathbf{A}$. We will try to solve the following more general problem: given $t$, determine the $t$'th smallest element in $\mathbf{A}$.

Let $m_r = \min(m_1,\ldots,m_k)$ and $m_s = \max(m_1,\ldots,m_k)$. Define $$ N = \sum_{i=1}^k \lceil |A_i|/2 \rceil. $$ There are at least $N$ many elements in $\mathbf{A}$ whose value is at least $m_r$, and at least $N$ many elements in $\mathbf{A}$ whose value is at most $m_s$. 

If $N \geq t$ then elements larger than $m_s$ cannot be the $t$'th smallest element. In particular, we can throw out the upper half of $A_s$. Similarly, if $N \geq n+1-t$ then elements smaller than $m_r$ cannot be the $t$'th smallest element, and so we can throw out the lower half of $A_r$ (and update $t$ accordingly, by subtracting $\lfloor |A_r|/2 \rfloor$). Note that $\min(t,n+1-t) \leq \lceil n/2 \rceil \leq N$, and so at least one of these cases must happen.

How many rounds does it take this algorithm to complete? Each round results in reducing the size of one of the $k$ arrays roughly by half (the reduction is $\ell \mapsto \lceil \ell/2 \rceil$). One can check that it takes $\lceil \log \ell \rceil$ steps to reduce each array to a singleton. Therefore the number of rounds it takes the algorithm to narrow down all arrays to a single element is $$ \sum_{i=1}^k \lceil \log |A_i| \rceil \leq k + \sum_{i=1}^k \log |A_i| \leq k + k \log \sqrt[k]{|A_1| \cdots |A_k|} \leq k + k \log \frac{|\mathbf{A}|}{k}. $$ After an initial round which takes $O(k\log k)$ time, each subsequent round can be implemented in $O(\log k)$, if we store the medians in an appropriate data structure such as a heap. Following this phase, we are left with $k$ elements, and we can run a linear time selection algorithm to find the $t$'th smallest element in $O(k)$. In total, this algorithm runs in time $$ O\bigl(k\log k + k \log \tfrac{|\mathbf{A}|}{k}\bigr) = O(k\log |\mathbf{A}|). $$ When $|\mathbf{A}_i|=n$ for all $i$, this is $O(k\log (kn))$.