As Gerald says, the answer is no without further hypotheses on f. But if one makes some minimal additional regularity hypotheses on f, such as continuity, then the answer is yes.

Write $D_h f(x)$ for the difference quotient $D_h f(x) := (f(x+h)-f(x))/h$, then the hypothesis is that $$ D_h f(x+h) = D_h f(x) + O( |h|^{1/2} )$$ for all $x, h$ (with $h$ nonzero), which implies $$ D_{2h} f(x) = D_h f(x + ih) + O( |h|^{1/2} )$$ for $i=0,1$. Iterating this we have $$ D_{2^j h} f(x) = D_h f(x + ih) + O( 2^{j/2} |h|^{1/2} ) \qquad (1)$$ for natural numbers $j$ and any integer $0 \leq i < 2^j$, which in particular implies $$ D_h f(x+ih) = D_h f(x) + O( |ih|^{1/2} ) \qquad (2)$$ for all integer $i$; in particular, we have $$ D_{(y-x)/n} f(y) = D_{(y-x)/n} f(x) + O( |y-x|^{1/2} )$$ for any distinct $x,y$ and natural number $n$. This already gives the derivative bound $|f'(y)-f'(x)| = O( |y-x|^{1/2} )$ if $f$ is differentiable.

To establish differentiability, we return to (1). Telescoping this using binary expansion (and (2)) we have $$ D_{nh} f(x) = D_h f(x) + O( |nh|^{1/2} )$$ for any integer $n$ (not necessarily a power of two, noting that $D_{-nh} f(x) = D_{nh} f(x+nh)$), and thus $$ D_{h} f(x) = D_{h/n} f(x) + O( |h|^{1/2} )$$ for any non-zero $h$ and nonzero integers $n$. In particular $$ D_{h} f(x) = D_{h'} f(x) + O( |h|^{1/2} + |h'|^{1/2} )$$ whenever $h,h'$ are nonzero rational (as then we can write $h = n h'', h' = n' h''$ for some nonzero integers $n,n'$ and some nonzero $h'$); by continuity of $f$, this is also true for nonzero real $h,h'$. Thus $D_h f$ is a Cauchy sequence as $h \to 0$, giving differentiability.

It is likely that one can also relax continuity to Lebesgue measurability (it seems that the above argument gives almost everywhere differentiability or something very close to this, in which case some version of the fundamental theorem of calculus should then finish the job).

As Gerald says, the answer is no without further hypotheses on f. But if one makes some minimal additional regularity hypotheses on f, such as continuity, then the answer is yes.

Write $D_h f(x)$ for the difference quotient $D_h f(x) := (f(x+h)-f(x))/h$, then the hypothesis is that $$ D_h f(x+h) = D_h f(x) + O( |h|^{1/2} )$$ for all $x, h$ (with $h$ nonzero), which implies $$ D_{2h} f(x) = D_h f(x + ih) + O( |h|^{1/2} )$$ for $i=0,1$. Iterating this we have $$ D_{2^j h} f(x) = D_h f(x + ih) + O( 2^{j/2} |h|^{1/2} ) \qquad (1)$$ for natural numbers $j$ and any integer $0 \leq i < 2^j$, which in particular implies $$ D_h f(x+ih) = D_h f(x) + O( |ih|^{1/2} ) \qquad (2)$$ for all integer $i$; in particular, we have $$ D_{(y-x)/n} f(y) = D_{(y-x)/n} f(x) + O( |y-x|^{1/2} )$$ for any distinct $x,y$ and natural number $n$. This already gives the derivative bound $|f'(y)-f'(x)| = O( |y-x|^{1/2} )$ if $f$ is differentiable.

To establish differentiability, we return to (1), which (in combination with (2)) gives $$ f(x+(i+2^j)h) - f(x+ih) = 2^j h D_h f(x) + O( |2^j h|^{3/2} )$$ whenever $i = O( 2^j )$. Telescoping this using binary expansion we see that $$ f(x+nh) - f(x) = n h D_h f(x) + O( |nh|^{3/2} )$$ or equivalently $$ D_{nh} f(x) = D_h f(x) + O( |nh|^{1/2} )$$ for any integer $n$ (not necessarily a power of two), and thus $$ D_{h} f(x) = D_{h/n} f(x) + O( |h|^{1/2} )$$ for any non-zero $h$ and nonzero integers $n$. In particular $$ D_{h} f(x) = D_{h'} f(x) + O( |h|^{1/2} + |h'|^{1/2} )$$ whenever $h,h'$ are nonzero rational (as then we can write $h = n h'', h' = n' h''$ for some nonzero integers $n,n'$ and some nonzero $h'$); by continuity of $f$, this is also true for nonzero real $h,h'$. Thus $D_h f$ is a Cauchy sequence as $h \to 0$, giving differentiability.

It is likely that one can also relax continuity to Lebesgue measurability (it seems that the above argument gives almost everywhere differentiability or something very close to this, in which case some version of the fundamental theorem of calculus should then finish the job).