You say 'only millions records'. Even if you had 2^36 records (that's over 68 billion) the chances of a collision should be 0.0000000000000004

That really is vanishingly small.

So, rationally, I'd guess it is more likely there is a problem with the implementation of UUID you are using, or just perhaps there is some other cause of the collision...like a bug?