This problem has a probabilistic interpretation. Namely, if one considers the Markov chain on the integer points in the rectangle $[0,N]\times [0,M]$ with the transition probabilities
$$
p\bigl((i,j),(i,j-1)\bigr) = \frac{N-i}{N} \;, \qquad p\bigl((i,j),(i-1,j)\bigr) = \frac{i}{N} \;,
$$
then $f(i,j)$ is the expected number of steps until the chain attains the horizontal line $\{j=0\}$ where it is absorbed. Now, the $i$ component of this chain is the Markov chain on $[0,N]$ with the transition probabilities
$$
p(i,i) = \frac{N-i}{N} = p_i \;, \qquad p(i,i-1) = \frac{i}{N} = 1-p_i\;,
$$
which can be interpreted as the deterministic chain $i\to i-1$ with additional "holding" at each state. The distribution of this holding time at a point $i$ is geometric with the parameter $1-p_i$, i.e., the holding time is 0 with probability $1-p_i$, is 1 with probability $p_i(1-p_i)$, etc. Thus, the expectation of the holding time at point $i$ is $p_i/(1-p_i)$, and the expected vertical displacement of the original chain provided its horizontal component attains a point $t\in [0,n]$ is
$$
M_t=\frac{p_N}{1-p_N} + \dots + \frac{p_t}{1-p_t} = \frac{1}{N-1} + \dots + \frac{t}{N-t} \sim \int_0^t \frac{x}{N-x}dx = N\log\frac{N}{N-t}-t \;.
$$
In particular, if $t$ is close to $N$, then $M_t\gg N>M$, which means that our chain most likely becomes absorbed before it attains the vertical segment $\{i=0\}$. [More rigorously here one should also estimate the variance of the vertical displacement to make sure it does not differ much from $M_t$.]
Now the equation
$$
M = N\log\frac{N}{N-t}-t
$$
will give us the likely number of horizontal steps $t$ necessary to have vertical displacement $M$, i.e., to be absorbed. The total expected time before absorption will be therefore
$$
f(N,M)=M + t = N\log\frac{N}{N-t} \;.
$$
The above equation can be rewritten as
$$
\frac{M}{N} = -\log (1-t/N) - t/N \;.
$$
Under the assumption that $M \ll N$ (i.e., $t \ll N$) one can expand the log in the RHS, which gives
$$
\frac{M}{N} \approx \frac{t^2}{2N^2} \;,
$$
whence $t\approx\sqrt{2MN}$ and $f(N,M)\approx\sqrt{2MN}$.