Let $K_{m,n}$ be a complete bipartite graph. We need to find a way to embed $K_{m,n}$ on a surface $S$. We need to show that, if $$\chi (S) \leq m+n - \frac{mn}2\,,\tag{#}$$ then an embedding is possible. Here, $\chi (S)$ is the Euler characteristic of the surface $S$.
By attempting at the problem, I think the converse (i.e., if there exists an embedding of $K_{m,n}$ into $S$, then (#) holds) is true. Here is my proof (if it is correct).
Suppose that an embedding is possible. Write $F$ for the set of all faces of $G:=K_{m,n}$. Since a bipartite graph has no odd cycles, each face has degree at least $4$. Therefore, $$2|E|=\sum_{f\in F}\,\deg(f)\geq 4|F|\,,$$ where $E$ is the set of all edges of $G$. Thus, $|F|\leq \dfrac{|E|}{2}$. Now, $$\chi(S)\,\overset{\color{red}{(*)}}{\color{red}{=\!=}}\,|V|-|E|+|F|\leq |V|-|E|+\dfrac{|E|}{2}=|V|-\frac{|E|}{2}\,,$$ where $V$ is the set of all vertices of $G$. Since $|V|=m+n$ and $|E|=mn$, we obtain $$\chi(S)\leq (m+n)-\frac{mn}{2}\,.$$
Thanks in advance.
Remark (by Batominovski). The equality (*) is dubious, and is unlikely true.
First of all, let me try to make sense of the question. A graph embeds in a planar surface if and only if it embeds in a plane. Of course, by puncturing the plane, you can get as low Euler characteristic as you like, hence, the answer to the stated question is negative for all $m, n\ge 3$. I strongly suspect that you meant to ask about $S\subset R^3$. Of course, every open surface embeds to $R^3$, so a meaningful question would be about $S$ which is closed (compact with empty boundary) and connected. Such a surface embeds in $R^3$ if and only if it is oriented. In equivalent form, you are asking about the genus of $K_{n,m}$:
Definition. The genus $g=g(\Gamma)$ of a graph $\Gamma$ is the smallest genus of an oriented surface in which $\Gamma$ embeds.
For graphs $K_{n,m}$ the genus is computed by Ringel's formula: $$ g(K_{n,m})= \lceil (m-2)(n-2)/4 \rceil, $$ assuming $n, m\ge 2$.
In terms of the Euler characteristic, your guess is almost correct, since, assuming $g=(m-2)(n-2)/4$ is integral, $$ 2-2g= m+n- \frac{mn}{2}. $$ In particular, if $K_{n,m}$ embeds in $S$, then indeed $\chi(S)\le m+n- \frac{mn}{2}$.
Edit. Ringel also proved the formula for non-orientable genus: $$ q(K_{n,m})=\lceil (m-2)(n-2)/2 \rceil, $$ provided that $n, m\ge 3$. The Euler characteristic formula then is: $$ \chi(N_q)=2-q= m+n- \frac{mn}{2}. $$ (assuming integrality).
Ringel's original article was in German. You can find an English-language proof in:
André Bouchet, Orientable and nonorientable genus of the complete bipartite graph, Journal of Combinatorial Theory, Series B, Volume 24, Issue 1, February 1978, Pages 24-33.