There are at least $kmn$ edges colored in the most used color. We delete the remaining edges and prove that there exists a connected component with at least $m+n$ vertices in the remaining graph. The idea is to consider all the connected components. If each one has less than $m+n$ vertices, then the graph is too fragmented and it's impossible to have too many (at least $kmn$) edges even if all edges are present in every connected component. It boils down to prove a certain inequality.

Lemma. Let $x, y$ be two positive real numbers and $\ell, k$; $\ell \ge k$ be natural numbers. Let $x_i, y_i, i = 1, 2, \dots, \ell$ satisfy the following conditions.
$$x_i \ge 0, y_i \ge 0, x_i + y_i \le (x+y)/k, i = 1, 2, \dots, \ell;$$
$$\sum_{i=1}^{\ell} x_i = x, \quad \sum_{i=1}^{\ell} y_i = y. \qquad (1)$$
Then it holds
$$\sum_{i=1}^{\ell} x_i y_i \le \frac{xy}{k}.$$
The equality is reached only if $x_i = x/k, y_i = y/k, i = 1, 2, \dots, k$; $x_i = y_i = 0, i > k$.
Proof. Let us denote $f(x, y) := \sum_{i=1}^{\ell} x_i y_i$, where $x = (x_1, \dots, x_{\ell})$, $y = (y_1, \dots, y_{\ell})$. The conditions in (1) determine a compact set, hence $f$ attains its maximum value on it, say, at the points $x'_i, y'_i, i = 1, 2, \dots, \ell$. We can assume $x'_1 \ge x'_2 \ge \dots \ge x'_{\ell}$. We shall prove that $y'_i$ are also in decreasing order. Let us assume on the contrary that $y'_i < y'_{i+1}$. Set
$$x_i = x_{i+1} := (x'_i + x'_{i+1})/2; \quad y_i = y_{i+1} := (y'_i + y'_{i+1})/2.$$
Then (Chebyshev inequality)
$$x_i y_i + x_{i+1} y_{i+1} > x'_i y'_i + x'_{i+1} y'_{i+1}.$$
But it contradicts the maximality of $x'_i, y'_i, i = 1, \dots, \ell$. Next, if $x'_1 + y'_1 < (x+y)/k$ we can similarly set $x_1 := x'_1 + \varepsilon, x_2 := x'_2 - \varepsilon; y_1 := y'_1 + \delta, x_2 := x'_2 - \delta$ for sufficiently small $\varepsilon, \delta \ge 0$ and get a larger value of $f$. Therefore, $x'_1 + y'_1 = (x+y)/k$.
Let $k'$ be the largest index for which $x_{k'} > 0$ and $y_{k'} > 0$. In the same way we can see that $x'_i + y'_i = (x+y)/k, i = 1, 2, \dots, k'$. Hence, $k' \le k$. Assume that $k' < k$ and $y_i = 0, i > k'$. We modify $x', y'$ as follows. Set
$$x_i := x'_i, y_i := y'_i, i = 1, 2, \dots, k' - 1; \\ x_{k'} := x'_{k'}, y_{k'} := y'_{k'} - \varepsilon, x_{k'+1} := (x+y)/k, y_{k'+1} := \varepsilon.$$
For $i > k' + 1$ we set $y_i = 0$, and the values of $x_i, i > k' + 1$ are irrelevant providing they comply with (1). Since $x'_k < (x+y)/k$, it can be seen that $f(x, y) > f(x', y')$ which contradicts the maximality of $x', y'$.
Thus, $k' = k$. We prove that $x'_i = x/k, y'_i = y/k, i = 1, 2, \dots, k$. Assume on the contrary it doesn't hold and let $j$ be the first index for which $x'_j \ne x/k$. WLOG let $x'_j < x/k$. Then there exists $i > j$ for which $x'_i > x/k$. This means $x'_i > x'_j$ and thus the sequence $x'_1, x'_2, \dots, x'_k$ is not decreasing, contradiction. To recap, we established that $x'_i = x/k, y'_i = y/k, i = 1, 2, \dots, k$. In this case $f(x', y') = kxy$, and Lemma 1 is proved. $\square$

Back to the problem. The number of all edges of $K$ is $k^2mn$, hence there is a color, say, white such that at least $kmn$ edges are colored white. We delete all edges colored in a color other than white. We'll prove that in the remaining graph $K'$, there exists a connected component with at least $m+n$ vertices. Assume on the contrary it is not true. Denote the connected components of $K'$ by $G(A_i, B_i)$, $i = 1, 2, \dots, \ell$ and let $|A_i| = m_i, |B_i| = n_i, i = 1, 2, \dots, \ell$. We have
$$\sum_{i = 1}^\ell m_i = km, \quad \sum_{i=1}^\ell n_i = kn, m_i + n_i < m + n.$$
According to Lemma 1,
$$\sum_{i=1}^{\ell} m_i n_i < kmn$$
which contradicts the choice of the white color. This means that for at least one index $i$ it holds $m_i + n_i \ge m + n$.