A function with a non-negative upper derivative must be increasing?

The statement is not true. The Weierstrass function has upper derivative greater than zero everywhere, it is continuous, and it is not an increasing function. This question comes as an error in Royden, and should read that the lower derivative of $f$ is greater than or equal to zero, per this errata.

http://www2.math.umd.edu/~pmf/docs/Real%20Analysis.pdf

Probably not the best approach, but here is an idea: show taht MVT holds in this case:

Lemma Let $[c,d]$ be a subinterval of $[a,b]$. Then there exists a point $e \in [c,d]$ so that

$$\frac{f(d)-f(c)}{d-c}=\overline{D}f(e)$$

Proof:

Let $g(x)=f(x)-\frac{f(d)-f(c)}{d-c}(x-c) \,.$

Then $g$ is continuous on $[c,d]$ and hence it attains an absolute max and an absolute minimum. Since $g(c)=g(d)$, then either $g$ is constant, or one of them is attatined at some point $e \in (c,d)$.

In the first case you can prove that $\overline{D}g=0$ on $[c,d]$, otherwise it is easy to conclude that $\overline{D}g(e)=0$.

Your claim follows immediately from here.

This is based on David's comment above.

Choose $u,v, \epsilon$ such that $ a < u < v < b$ and $ \epsilon > 0 $.

Let $$ S = \{ x \in [u,v] : f(x) + \epsilon x \geq f(u) + \epsilon u \}.$$ $S$ is not empty as $ u \in S$ and $S$ is closed as $f$ is continuous.

Let $\sup S = t$, $t$ is in $S$ as $S$ is closed. We will show $t=v$.

If $ t < v$, then define for $ \delta \in (0, v- t] $, $g(\delta) = \sup_{0 < h \leq \delta} \dfrac{f(t+h) - f(t)}{h}$.

Since $g(\delta)$ decreases to $\overline{D}f(t) \geq 0$ as $ \delta \to 0^+$, we must have $ g(\delta) > -\epsilon $ for sufficiently small positive $\delta$, and this means, the set $g(\delta)$ is a supremum of, must contain an element greater than $-\epsilon$. Hence there is a $t_1 \in (t,v]$ with $\dfrac{f(t_1) - f(t)}{t_1 - t} > -\epsilon$, we have $f(t_1) + \epsilon t_1 > f(t) + \epsilon t \geq f(u) + \epsilon u$, i.e., $t_1 \in S$. This contradiction implies $v = \sup S$ and $f(v) \geq f(u ) + \epsilon (v - u)$. Letting $\epsilon \to 0$, we have $f(v) \geq f(u)$. Hence $f$ is non-decreasing on $(a,b)$. This can be extended to all of $[a,b]$ by keeping $v$ fixed and letting $u \to a$ and keeping $u$ fixed and letting $v \to b$.