Fréchet differentiability from Gâteaux differentiability
It seems worth expanding user31373's answer above for the benefit of those who could come to this page by chance (as I did).
The Mean Value theorem discussed above is the following statement:
Let $f : X \to Y$ be a map of normed linear spaces. Given $x_0 \in X$ and a direction $h \in X$ such that the directional derivative $\delta f(x_0+th)(h)$ exists for all $t \in [0,1],$ we have that $$ \|f(x_0+h)-f(x_0)\| \leqslant \|\delta f(x_0+th)(h)\| $$ for a suitable $t \in [0,1]$
(P.Drabek, J.Milota, Methods of Nonlinear Analysis, 2007; Th. 3.2.7). It follows that \begin{equation} \tag{$*$} \|f(x_0+h)-f(x_0)-\delta f(x_0)h\| \leqslant \|\delta f(x_0+th)(h)-\delta f(x_0)(h)\| \end{equation} (the latter statement is left without the proof in Drabek--Milota, and, unfortunately, the hint that is given there is misleading; however the book is one of the best sources on Fréchet and Gâteaux differentiation). In fact, one can use the idea from user31373's answer. We consider the map $g : X \to Y$ such that $$ g(x)=f(x)-\delta f(x_0)(x-x_0) $$ for all $x \in X.$ It is easy to see that the Mean Value theorem applied to $g$ gives us $(*).$ Let us verify, for instance, the key fact of existense of the directional derivatives $\delta g(x_0+th)(h).$ First, recall that the Gâteaux differential preserves the scalar multiplication: $\delta f(x)(r h)=r \delta f(x)(h)$ for all $x,h \in X$ and for all $r \in \mathbf R$ (the homogeneity of $\delta f(x)$). We have that \begin{eqnarray} \delta g(x_0+th)(h) &=& \lim_{u \to 0} \frac{g(x_0+th+uh)-g(x_0+th)}u \\ &=&\lim_{u \to 0} \frac{f(x_0+th+uh)-\delta f(x_0)( (t+u)h) - f(x_0+th)+\delta f(x_0)(th)}u \\ &=&\delta f(x_0+th)(h)-\delta f(x_0)(h) \end{eqnarray} where we have used the homogeneity to justify the last equation.
Now to address the question under what conditions existense of Gâteaux differentials implies existense of Fréchet differential. The standard result is the following one (quoting again Drabek--Milota):
if $f : X \to Y$ is a map of linear normed spaces such that in a certain open neighbourhood $O_{x_0}$ of $x_0 \in X$ the Gâteaux differential $\delta f(x)$ exists and is linear and continuous for all $x \in O_{x_0}$ and the map $$ x \mapsto \delta f(x) $$ from $X$ into $L(X,Y) $ is continuous at $x_0,$ then $f$ is Fréchet differentiable at $x_0$
(Prop. 3.2.15 in Drabek--Milota); $L(X,Y)$ is the normed space of continuous linear maps from $X$ to $Y$ equipped the uniform norm $$ \|\varphi\| =\mathrm{sup}_{x \ne 0} \frac{\|\varphi(x)\|}{\|x\|} \qquad (\varphi \in L(X,Y)). $$ The proof is based on the equality $(*)$ above.
Theorem 1-2 from Saaty's "Modern Nonlinear Equations" proves this using a combination of the mean value theorem and the Hahn Banach Theorem.
My understanding of the problem: we know that the Gâteaux derivative exists and is continuous; we want to prove that it is actually the Fréchet derivative. Pick a point $x_0$. Subtract a linear functional from $f$ so that $f\,'(x_0)=0$. For any $\epsilon>0$ there is a neighborhood of $x_0$ in which $|f\,'|<\epsilon$. By the Mean Value theorem $|f(x)-f(x_0)|\le \epsilon |x-x_0|$ in this neighborhood. Hence $f\,'(x_0)=0$ in the Fréchet sense.