What is the codimension of matrices of rank $r$ as a manifold?

Since you asked, I've replaced my hint with a full solution:

First consider matrices of the form

$$A = \begin{pmatrix} B & C\\ D & E \end{pmatrix}$$

Where $B$ is an $r \times r$ nonsingular matrix. Since invertibility is an open condition, this set of such matrices, denoted $Z$, is a submanifold of $M_{m \times n}$. Postmultiply by the nonsingular matrix

$$\begin{pmatrix} I & -B^{-1}C\\ 0 & I \end{pmatrix}$$

to obtain the matrix

$$\begin{pmatrix} B & 0\\ D & -DB^{-1}C + E \end{pmatrix}$$

the original matrix has rank $r$ iff this new matrix has rank $r$, which is clearly only the case if $-DB^{-1}C + E = 0$. Thus we can define a map $f$ from $Z$ to matrices of size $(m-r) \times (n-r)$ that sends $A$ as above to $-DB^{-1}C + E$. This is clearly smooth, so it suffices to check that it is a submersion. Now, the tangent space of the image is the same space as the image, since the image is a linear space. Let $X$ be an $(m-r) \times (n-r)$ matrix. Consider the curve passing through any matrix $A \in Z$.

$$\gamma(t) = \begin{pmatrix} B & C\\ D & E+tX \end{pmatrix}$$

The derivative of $f \circ \gamma$ at $0$ is $X$, and this is equal to

$$df_{A}(\begin{pmatrix} 0 & 0\\ 0 & X \end{pmatrix})$$

so that at any arbitrary point $A$ we have shown the existence of a tangent vector at $A$ that is mapped by $df$ to $X$. This verifies that $f$ is submersion, and hence $f^{-1}(0)$ is a smooth submanifold of $\mathbb{R}^{mn}$. The dimension $f^{-1}(0)$ is $mn - (m-r)(n-r)$, i.e. of codimension $(m-r)(n-r)$.

Of course, we have only shown that matrices of rank $r$ contained in $Z$ form a smooth submanifold. However, any matrix can be put into the form of matrices in $Z$ by rearranging rows and columns, which is just a linear isomorphism. Thus if $A$ is matrix of rank $r$, we have a map $R$ to a matrix in $Z$ contained in chart $\psi$. Then we have that $\psi \circ R$ is a smooth chart around $A$ inherited from a chart on $M_{m \times n}$. The collection of these charts then extends to a maximal atlas giving the set of rank-$r$ matrices the structure of a smooth submanifold.

This answer was originally going to be a comment on Bruno Joyal's answer, but it got too long.

As you suggest, a natural way to try proving something like this is to use the preimage theorem. So we want a map $F$ from $m \times n$ matrices to $(m-r)(n-r)$ space such that $d F$ is surjective and $F^{-1}(0)$ is, more or less, the matrices of rank $r$. (Why do I say more or less? First of all, the matrices of rank $r$ contain the matrices of rank $<r$ in their closure, and $F^{-1}(0)$ will be closed, so we can't exactly hope to get the matrices of rank $r$. And, in fact, our solution will only work in the open submanifold $Z$ introduced by Isaac Solomon.)

One natural idea is to send a matrix $M$ to all of its $(r+1) \times (r+1)$ minors; $M$ is rank $r$ if and only if all of these minors vanish. But there are $\binom{m}{r+1} \times \binom{n}{r+1}$ of these, way more than $(m-r)(n-r)$, and $dF$ is not surjective.

Can we cleverly choose $(m-r) \times (n-r)$ of the minors to use? Yes! Let $Z$ be the open submanifold where the upper leftt $r \times r$ sumbmatrix is invertible. I'll write $B$ for this upper left matrix. Let $F: \mathrm{Mat}_{m \times n} \to \mathrm{Mat}_{(m-r) \times (n-r)}$ send a matrix $M$ to the matrix $F(M)$ whose $(i,j)$ entry is the minor using row $i+r$ together with the first $r$ rows, and column $j+r$ together with the first $r$ columns.

I claim $dF$ is surjective. Proof: We'll show that the $(m-r) \times (n-r)$ matrix $\left( \partial F_{ij}/\partial M_{k \ell} \right)$ where $k$ and $\ell>r$ is an isomorphism. If $(k, \ell) \neq (i+r, j+r)$, then $M_{k \ell}$ does not occur in the minor $F_{ij}$, so $\partial F_{ij}/\partial M_{k \ell}=0$. If $(k, \ell) = (i+r, j+r)$, then expanding by minors in the last row, $\partial F_{ij}/\partial M_{k \ell} = \det B \neq 0$. So the matrix of partials $\left( \partial F_{ij}/\partial M_{k \ell} \right)$ is diagonal with nonzero entries on the diagonal.

Now, I claim that $F^{-1}(0) \cap Z$ is the set of rank $r$ matrices in $Z$. I'm going to skip this one. Basically, we can apply downward and leftward row and column operations to $M$ to put it in the form $\left( \begin{smallmatrix} B & 0 \\ 0 & N \end{smallmatrix} \right)$ without altering the minors $F_{ij}$. So we have a proof by using a set of $(m-r) \times (n-r)$ minors, rather than by G and P's trick.

The fun thing is that I believe these proofs are basically the same proof! I think that $F(M) = (\det B) (E - D B^{-1} C)$ and the row and columns operations I referred to in the previous paragraph are the $2 \times 2$ matrices G and P use. So the question is whether to write the proof using

Another approach: A matrix has rank $<r$ if and only if all of its $r \times r$ minors have zero determinant. An $m\times n$ matrix has $(m-r)(n-r)$ minors of size $r \times r$ (choose which rows and columns to exclude). Together, the determinants of these minors give a polynomial map $\mathbf R^{m \times n} \to \mathbf R^{(m-r) \times (n-r)}$ whose zero set is precisely the set of matrices of rank $< r$...