Let $\left\{ u_1, \dots , u_n\right\}$ be a basis of $E$. Then, $\left\{ Au_1, \dots , Au_n \right\}$ is a system of generators of the subspace $\mathrm{im} A \subset F$. Whenever you have a system of generators of a vector (sub)space, you can delete some of them in order to obtain a basis. Since $r= \mathrm{rank} A = \mathrm{dim}\ \mathrm{im}A$, you can take $r$ of those $Au_i$ to form a basis of $\mathrm{im}A$. Reordering the original basis $u_1, \dots , u_n$ if necessary, we can assume that these are the first ones. So $Au_1, \dots , Au_r$ are a basis of $\mathrm{im}A$.
Now, you have $r\leq m$ linearly independent vectors $Au_1, \dots , Au_r$ in $F$. You can always complete a set of linearly independent vectors in order to order to obtain a basis of your vector space. So, choose $m-r$ vectors $v_{r+1}, \dots , v_m \in F$ such that $Au_1, \dots , Au_r, v_{r+1}, \dots , v_m$ is a basis of $F$.
And you're done: $\left\{ u_1, \dots , u_n\right\} \subset E$ and $\left\{ Au_1, \dots , Au_r, v_{r+1}, \dots v_m\right\} \subset F$ are bases you were looking for.
EDIT. I'm afraid my answer is wrong. If you perform the steps in it, the matrix you'll obtain looks like
$ \begin{pmatrix} 1 & 0 & \dots & 0 & a^1_{r+1} & \dots & a^1_n \\ 0 & 1 & \dots & 0 & a^2_{r+1} & \dots & a^2_n \\ \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 & a^r_{r+1} & \dots & a^r_n \\ 0 & 0 & \dots & 0 & 0 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 0 & 0 & \dots & 0 \end{pmatrix} $
But you have no control on the remaining $a^i_j$.