Runtime of Gaussian elimination/row reduction on an $m times n$ matrix

It is $Theta(mnmin(m,n))$, big-times-small-squared.

To get the row echelon form, each step $k=0,1,dots,min(m,n)-1$ updates a $(m-k)(n-k)$ panel by doing $O(m-k)(n-k)$ operations. So in particular each step takes at most $O(mn)$ flops, and at least half of them require at least $frac{m}{2}frac{n}{2}$ operations. These two bounds allow you to conclude.

For the additional steps for the reduced REF, the analysis is similar, up to a factor 2 because of the zeros. Although for stability reasons you'd better stop at the REF and then rely on back-substitution.