You are right, A can be non-square because A and AA^t both have the same number of rows. To prove that A and AA^t have the same range you apply that if AA^Tv = 0 then v^TAA^Tv = 0, this implies that (A^Tv)^T (A^tv) = 0, so that A^Tv = 0 hence dim(nullspace AA^T) = dim(nullspace A^t) and so range(AA^T) = range(A^T).
The proof is (briefly): A and AA^T have the same rank. AA^T is a linear transformation of the columns in A and spans the same number of dimensions and is thus the same subspace. It applies to non-square matrices as well.