We can do this more generally for any determinantal variety, so just consider $n \times m$ matrices where we don't need to assume $n=m$. Naively, we could calculate the degree from a free resolution of the determinantal variety, but unfortunately that's a complicated procedure. For just the purposes of getting the degree, it suffices to use any rank $1$ module supported in the determinantal variety. It turns out there are such modules which are both Cohen-Macaulay and have a linear free resolution $F_\bullet$ (without the rank assumption, these are known as Ulrich, or maximally generated maximal Cohen-Macaulay (MGMCM), modules in the literature). This is good because then ${\rm rank}(F_i) = {\rm rank}(F_0) \cdot \binom{c}{i}$ where $c = (n-r)(m-r)$ is the codimension of the determinantal variety. But then an easy computation with Hilbert series shows that the degree of the determinantal variety must be ${\rm rank}(F_0)$.

The complex is described in Exercise 6.34 of Weyman, *Cohomology of Vector Bundles and Syzygies*. Here's a brief construction: let $k^n \to k^m$ be the generic matrix thought of as a 2-term chain complex with $k^m$ in homological degree $0$. Apply the Schur functor $S_{(m-r) \times (n-r)}$ (here $(m-r) \times (n-r)$ means the rectangular partition $(n-r, n-r, \dots, n-r)$ repeated $m-r$ times). Then we get a complex (Schur functors can be used in any symmetric monoidal Abelian category, here our category is chain complexes) which has homology only in degree $0$ (and this is the rank $1$ module we were looking for) and the $0$th term is the representation $S_{(m-r) \times (n-r)}(k^m)$, which specializes to your example. The homology vanishing requires some work, but it can be proven using standard commutative algebra techniques (the Buchsbaum-Eisenbud acyclicity criterion) and some properties of Schur complexes. A bonus is that all of what I said is independent of characteristic (unlike the resolution of the coordinate ring of the determinantal variety!). Now, to advertise my own work, this has been generalized from determinantal varieties to matrix Schubert varieties: http://arxiv.org/abs/1006.5514 using the Schubert functors of Kraskiewicz and Pragacz: http://dx.doi.org/10.1016/j.ejc.2003.09.016

Finally, let me address the comment asking about (skew-)symmetric matrices. The same technique works here, and is partially discussed in Exercises 6.35 annd 6.36 of Weyman's book. The only difference is that we use staircase partitions instead of rectangular partitions, and the module won't have rank $1$, but some power of $2$, which can be calculated.

First consider the case of symmetric $n \times n$ matrices of rank at most $r$. This has codimension $\binom{n-r+1}{2}$. The staircase partition you want is $(n-r, n-r-1, \dots, 1)$ (the size of the partition is the codimension). We apply the corresponding Schur functor to the generic symmetric matrix $(k^n)^* \to k^n$. Again it has no homology in positive degrees and its $0$th term is $S_{(n-r, n-r-1, \dots, 1)}(k^n)$. The rank of its $0$th homology is $2^d$ where $d=\binom{n-r}{2}$. So the degree is $2^{-d} \dim(S_{(n-r,n-r-1,\dots,1)}(k^n))$. Sanity check: when $r=n-1$, the partition is $(1)$, so the complex is just the generic symmetric matrix, and the determinant has degree $n$.

Now we consider skew-symmetric $n \times n$ matrices of rank at most $r$. Now $r$ is even. This has codimension $\binom{n-r}{2}$. The staircase partition you want is $(n-r-1, n-r-2, \dots, 1)$. Do the same thing as above. The rank of the $0$th homology is $2^d$ where $d=\binom{n-r}{2}$. So the degree is $2^{-d} \dim(S_{n-r-1,n-r-2, \dots, 1}(k^n))$. Sanity check: when $r=n-2$, the partition is $(1)$ so the complex is just the generic skew-symmetric matrix, and the Pfaffian has degree $n/2$.

The formulas for (skew-)symmetric matrices can also be found in a paper of Harris and Tu: http://dx.doi.org/10.1016/0040-9383(84)90026-0 though it's stated in a different, but closely related, form. There are also some formulas in Enright and Hunziker (section 6) which don't just give the degree, but the numerator of the Hilbert series in terms of dimensions of some representations: http://dx.doi.org/10.1016/S0021-8693(03)00159-5 but I don't see how to specialize those formulas to get the ones discussed here.