If $E$ is generated by $E_1$ and $E_2$, then $[E:F]\leq [E_1:F][E_2:F]$?

The space spanned by the union of the two bases is usually not closed under muliplication, so won't span a field.

Instead you should show that $$ \{a_ib_j\mid 1\le i\le n, 1\le j\le m\} $$ is a spanning set.

Show that the $F$-space $L$ spanned by that set (inside $K$) is closed under multiplication, and that any field containing both $E_1$ and $E_2$ must contain $L$. Then show that $L$ also contains the inverse of all its non-zero elements. There the assumption about finiteness of $n$ and $m$ is crucial. Therefore $L$ is the smallest field containing both $E_1$ and $E_2$.

Note that this spanning set is not always linearly independent over $F$. Anyway, the dimension of $L$ is at most $mn$, which is what you wanted to show.

The sum of the degrees in general is not going to be an upper bound. Consider $K = \Bbb{Q}(\sqrt[3]{2},e^{2\pi i/3})$. This is a degree $6$ extension of $\Bbb{Q}$. Take $E_1 = \Bbb{Q}(\sqrt[3]{2})$ and $E_2 = \Bbb{Q}(e^{2 \pi i/3})$. Then

$$[E_1 : \Bbb{Q}] + [E_2:\Bbb{Q} ] = 3 + 2 = 5$$

but $E = K$ that has degree $6$ over $\Bbb{Q}$.