Mean Value Inequality in Banach Space without Hahn-Banach or Integrals If $f : E \to F$ is a continuous map of Banach spaces, with bounded Fréchet derivative. Then
$x_0,x_1 \in E\Rightarrow \|f(x_1) − f(x_0)\| ≤ M\|x_1 − x_0\|$ where $M = \sup \|f'(x)\|.$ 
The most efficient way to prove this, as far as I know, is to apply Hahn-Banach. Alternatively, one starts with $g(t)= f(x_0 + t(x_1 − x_0));\ 0\le t\le 1$ and reduces the problem to the real case. But, of course, the Hahn-Banach theorem is a (relatively) big gun, and to do the integral if one uses $g$, then integration in Banach spaces must be dealt with (via regulated functions, for example.) 
The only elementary proof I have seen uses the dot product (Apostol, Rudin), but then of course, one must assume an inner product.
Below I sketch a very basic proof, but it required more effort than I expected, so my question is: can one get it cheaper, using only elementary means (very basic facts about normed spaces and the definition of derivative)?
Assume for convenience that $x_0=f(x_0)=0$ and consider the segment $\{tx_1:\ 0\le t\le 1\}.$ 
We have $\|f(x)\|\le M\|x\|+\|r(x)\|\cdot\|x\|$ where $\frac{\|r(x)\|}{\|x\|}\to 0$ as $x\to 0.$ 
So, if $\epsilon>0,$ we can choose $\delta>0$ such that $t\le \min \left(1,\frac{\delta}{\|x_1\|}\right)\Rightarrow \|f(tx_1)\| ≤ (M + \epsilon)t\|x_1\|$. To prove the claim, it will suffice to prove that $t=1$ satisfies this last inequality, so to that end, 
let $\tau=\sup\{r>0:\|f(tx_1)\| ≤ (M + \epsilon)t\|x_1\|\text{for all}\ t\in [0,r]\}$, so that $\tau\le 1$ and $\tau\in \{r>0:\|f(tx_1)\| ≤ (M + \epsilon)t\|x_1\|\text{for all}\ t\in [0,r]\}$ (because $f$ is continuous.)
Now, toward a contradiction, suppose that $\tau<1$ and choose $c>0$ and small enough so that $(\tau+c)x_1$ is on the segment. 
Now, there is a $\delta' > 0$ such that 
$\|f(x) − f(\tau x_1)\| \le (M + \epsilon)||x − \tau x_1\|<\epsilon$ whenever $\|x − \tau x_1\| <\delta'.$ 
So, since $\|(\tau + c)x_1 − \tau x_1\| = c\|x_1\|<\delta' $ if $c$ is small enough, we have, with $x=(\tau + c)x_1$, 
$\|f((\tau+c) x_1)-f(\tau x_1)\| \le (M+\epsilon)\|(\tau+c)x_1-\tau x_1\|=(M+\epsilon)\|cx_1\|$ 
and so finally,
$f((\tau+c)x_1)\le (M+\epsilon)\|cx_1\|+\|f(\tau x_1)\|\le $
$(M+\epsilon)\|cx_1\|+ (M+\epsilon)\|\tau x_1\|=(M+\epsilon)(c+\tau)\|x_1\|$, 
which contradicts the fact that $\tau$ is a supremum.
 A: Here is another proof. At the core, the arguments are similar to yours (but with fewer $\delta$s). 
Assume that there are $x_1,y_1\in E$ and $\epsilon>0$ such that 
$$
\|f(y_1)-f(x_1) \| > (M+\epsilon) \|y_1-x_1\|.
$$
By triangle inequality, one of the following inequalities are satisfied:
$$
\|f(y_1)-f(\frac{x_1+y_2}2) \| > (M+\epsilon) \|y_1-\frac{x_1+y_2}2\|,
$$
$$
\|f(\frac{x_1+y_2}2) - f(x_1)\| > (M+\epsilon) \|\frac{x_1+y_2}2-x_1\|.
$$
Inductively, we can construct elements $(x_n,y_n)$ on the line segment $[x_1,y_1]$ with $\|x_n-y_n\| = 2^{1-n} \|x_1-y_1\|$, $[x_{n+1},y_{n+1}]\subseteq[x_n,y_n]$ and
$$
\|f(y_n)-f(x_n) \| > (M+\epsilon) \|y_n-x_n\|.
$$
Then $x_n,y_n\to x$ for some $x\in [x_n,y_n]$. And
$$
\|f(y_n)-f(x_n) \| \le \|f(y_n)-f(x)\| + \|f(x_n)-f(x)\|.
$$
By Frechet differentiability of $f$ at $x$ there we get
for $n$ large enough
$$\begin{split}
\|f(y_n)-f(x_n) \| &\le \|f(y_n)-f(x)\| + \|f(x_n)-f(x)\| \\ 
&\le (M+\epsilon/2) (\|y_n-x\| + \|x-x_n\|) \\& = (M+\epsilon/2)\|y_n-x_n\|,
\end{split}$$
which is a contradiction.

Let me try a direct proof in the flavor of your post. The proof works just with Gateaux differentiability of $f$ (and does not need continuity). Let $x,h\in E$ be given. Let $\epsilon>0$. Define
$$
I = \{ t\in [0,1]: \|f(x+th)-f(x)\| \le (M+\epsilon) t\|h\|\}.
$$
Clearly, $0\in I$. Assume $[0,t]\subset I$ for some $t\ge0$. Then by Gateaux differentiability of $f$ at $x+th$,
there is $s_0>0$ such that
$$
\|f(x+(s+t)h)-f(x+th)\| \le (M+\epsilon) s\cdot \|h\|
$$
for $s \in (0, s_0)$. 
By triangle inequality,
$$
\|f(x+(s+t)h)-f(x)\| \le (M+\epsilon) (s+t)\cdot \|h\| \quad \forall s\in (0,s_0).
$$
Hence $[0,t+s_0)\cap [0,1]\subset I$. 
Now suppose $[0,t)\subset I$ for some $t>0$. By Gateaux differentiability of $f$ at $x+th$,
there is $s_0>0$ such that
$$
\|f(x+(t-s)h)-f(x+th)\| \le (M+\epsilon) s\cdot \|h\|
$$
for $s \in (0, s_0)$. Taking $s\in (0,s_0$ such that $t-s\in I$, and using triangle inequality as above, it follows $t\in I$ and $[0,t]\subset I$.
By induction on the reals, $I=[0,1]$: Assume $I\ne[0,1]$. Let $t = \inf [0,1]\setminus I$. Then $t\ne0$ because there is $s_0>0$ such that $[0,s_0)\subset I$. 
By definition of inf, $[0,t)\subset I$. Using the steps above: $[0,t]\subset I$, $[0,t+s_0)\subset I$ for some $s_0>0$.
Since $\epsilon$ in the definition of $I$ was arbitrary, the claim follows.
Using these arguments, one can prove for Gateaux differentiable $f$ the standard mean value inequality
$$
\|f(x+h)-f(x) \| \le \sup_{t\in [0,1)}\|f'(x+th)\| \|h\|,
$$
with supremum taken over the half-open interval. 
Can this be reduced to a supremum over the open interval $(0,1)$?
