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?
Also possibly a problem with the version of UUID used. A v1 UUID is somewhat likely to collide if machines share MAC addresses and/or have problematic clocks.
The likelihood of a v4 collision is tied to the strength of the platform's (crypto) RNG.
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?