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.
This is one of the typical cases where the most obvious reason something is true is because the associated algorithm cannot possibly fail.
Roughly speaking, the only way Gauss-Jordan can ever get stuck is if (at any intermediate point) there is a column containing too many zeroes, so there is no row that can be swapped in to produce a non-zero entry in the expected location. However, if this does happen, it is easy to see that the matrix is non-invertible, and since the row operations did not cause this, it must have been the original matrix that is to blame.
Best Answer
First we eliminate the first terms taking 3 of the first row from the second and 4 of the first row from the third, to get $$x+2y-3z=4$$ $$-7y+14z=-10$$ $$-7y+(s^{2}-2)z=s-14$$
Then we simply take 1 of the new second row from the new third row, and our transformed system is just $$x+2y-3z=4$$ $$-7y+14z=-10$$ $$(s^{2}-16)z=s-4$$
If $s=+4$, the last equation becomes $0=0$ and your set is underdetermined, with solution $$x=z+\frac{20}{7}, \quad y=2z+\frac{10}{7}$$ for any $z$. The solutions lie on a line.
If $s=-4$, the last equation becomes $0=-8$, and your set is overdetermined, with no solution.
If $s$ is any other value, then simply $z=\frac{1}{s+4}$ and the other variables can be found by back-substitution. This solution is unique.