Well,
Although this does not answer your particular question of whether the paper is rightand although I have no idea if anyone published the result, it seems rather straightforward to obtain the $O(x^{1/2+\epsilon})$ result for calculating the sum $\sum_{n \leq x} \mu(n)$ by using the same idea as in my answer to http://mathoverflow.net/questions/81443/fastest-algorithm-to-compute-the-sum-of-primes/81545#81545. Let as in that answer $\Phi(x)$ be a smooth test function such that $\Phi(x)=1$ for $x<0$ and $\Phi(x)=0$ for $x>1$. The difference here is that we consider a sum $$ \sum_{n\leq x} \mu(n) =\sum_{n=1}^\infty \mu(n)\Phi \left( \frac {n-x} {\sqrt x} \right ) - \sum_{x< n < x + \sqrt x } \mu(n) \Phi \left(\frac {n-x} {\sqrt x} \right)$$ over the Möbius function instead of a sum over primes. The first sum can be calculated by the integral $$ \sum_{n=1}^\infty \mu(n)\Phi \left( \frac {n-x} {\sqrt x} \right )= \frac 1 {2 \pi i} \int_{c-\infty i}^{c+\infty i} \frac 1 {\zeta(s)} \int_0^\infty \Phi \left(\frac{y-x}{\sqrt x} \right)f(y) y^{s-1} dyds, (c>1)$$ which can be calculated by the Odlyzko-Schönhage algorithm in time $O(x^{1/2+\epsilon})$ in the same way as in that answer. The remaining sum will be over an interval of length $\sqrt x$. Sieving techniques can determine the Möbius function for all these numbers fast and the time it will take to calculate that sum is of the order of $O(\sqrt x \log x)$.
Update: I looked at Lagarias-Odlyzkos 1987 paper "Computing $\pi(x)$ an analytic method". On page 8 at the bottom of the page I quote "The basic ideas underlying analytic $\pi(x)$ algorithms can be used for computing other arithmetical functions, such as $$ M(x) =\sum_{n\leq x} \mu(n).$$ Thus they were certainly aware of the $O(x^{1/2+\epsilon})$ time complexity for calculating $M(x)$. What I describe above is indeed a variant of the Lagarias-Odlyzko method.
