Precision problem on AMD
In HLSL, you can use the built-in fmod function for this.

I'm not sure what's going wrong with your implementation, though. It looks mathematically correct. It's conceivable you're encountering a precision issue with the subtraction, depending on the inputs.

BTW, an alternative implementation which avoids the subtraction is:

float Mod(float x, float y)
{
    return frac(x / y) * y;
}