The error is that E=Mcc is only part of the more complete relationship. Momentum is another term in the equation, but it usually is omitted because it usually is negligible unless M = 0, or is small relative to E.

A more complete equation is E^2 = (pc)^2 + (Mcc)^2, where p is the momentum.

Notice that where M >> 0, p is relatively small, so usually we ignore it. However, where M = 0, as in a photon for example, it still has momentum, even if it has no mass, as long as it has energy, which a photon certainly has. Where M is slightly greater than 0, but E is significiant, such as in an energetic neutrino, then it is not practical to ignore the value of (pc)^2