It depends on how efficient you want to be, and it also depends on the rank of the matrix. But for a "generic" matrix, you can expect the rank to be $\min(N,M)$, and for "most" entries to be nonzero. (And, do you count multiplying zero by a constant as a "multiplication"? Adding two zeros as an "addition"?)
I interpret your question as asking for the number of multiplications and additions of entries, rather than adding rows, etc.
Every time you multiply a row by a constant, you are performing $M$ multiplications (minus the number of entries that are zero if they don't count); every time you add a row to another row you are performing $M$ additions/subtractions (minus the number of entries that are zero in both).
So, generically, let us assume that the only zeros you will encounter are the ones you create throught Gauss-Jordan elimination.
So, how do you get started? First you pick a pivot; then you use that pivot to eliminate the other entries in the column; there are $N-1$ entries to be eliminated; each elimination requires (i) multiplying your pivot row by a constant; and (ii) adding the pivot row to another row. So you are performing $M$ products and $M$ sums in each step, and you are doing this $N-1$ times. Then, you multiply the first row appropriately to get a $1$ in the pivot, for another $M$ products.
Next you pick your next pivot, and you need to eliminate the entries below it on the column; there are $N-2$ entries; each entry requires (i) multiplying your pivot row by a constant, which requires $M-1$ products (first entry is $0$, you can ignore it), and then (ii) adding to the other row, requiring $M-1$ sums (first entry in both is $0$, you can ignore it). You do this $N-2$ times, and then multiply the first row by a constant ($M-1$ products again) to get a $1$ in the pivot.
Then you pick your next pivot... etc. Figure out how many products/sums we are doing in each step, how many steps, add them all up.
This will be an upper bound, since in practice you could end up with lots of zeros, or a matrix that has rank strictly smaller than $\min(M,N)$, so that you get a row of zeroes early on, etc.
Reading your title, though, you might be counting "add a row to another row" as a single step, and "multiply a row by a constant" as a single step; in that case, proceed as above but you only count the number of row operations instead of the number of individual numerical operations, and the number of common zeros between the rows is irrelevant.
Best Answer
First and foremost, $O$ is about giving an upper bound. Thus if you think it is $O(n^5)$ then it is also $O(n^7)$ and $O(n^6)$ and $O(n^{5.1})$ and $O(n^{2483624})$.
Second, it is not $O(n^5)$ as you cannot just ignore the logarithmic term there.
What you want to show is that there is a $C>0$ such that for all naturals $n$ (or for all sufficiently large $n$ it does not matter that much) you have $$n^5 \log n \le Cn^7.$$ This is true with $C=1$, as $\log n \le n$ for all $n \ge 1$ and thus $$ n^5 \log n \le n^5 n = n^6 \le n^7.$$
As you see the expression would also be $O(n^6)$, so the $n^7$ is indeed a bit arbitrarily chosen but its true. Just like $56$ is less than $60$ and also less than $70$.