Count elements of a sorted matrix that fall into a given interval
First, notice that you only need to know how to count the number of elements bigger than $k_{min}$, because then, by a very simple transformation, you can count the number of element smaller than $k_{max}$, and compute the desired result : since the set $A$ of element bigger than $k_{min}$ is of the form $[a;max]$, and the set $B$ of element smaller than $k_{max}$ is $[min;b]$, you have $|A \cap B| = |A| + |B| - n^2$

Now, find the last element smaller than $k_{min}$ on the last row, at column $c_0$.
On this last row, exactly $n - c_0$ elements are bigger than $k_{min}$.
On the row above, the last element smaller than $k_{min}$ has to be right to $c_0$, because otherwise, since $M$ is sorted on row and column, you would have a contradiction. Hence, in order to find the last element smaller than $k_{min}$ on this row, you can start at column $c_0$ and go right to find $c_1$.
Then again, the number of elements bigger than $k_{min}$ on this row is $n - c_1$.

Repeating this process, you then sum the number of elements on each row to compute the result, and you'll scan only at most $2n$ elements since the path followed by the algorithm is a path from the point $(0,n-1)$ to the point $(n-1,0)$, going only up and left, and these kind of path have length $2n$.
This is hence indeed an $\mathcal{O}(n)$ algorithm.

EDIT: details added