Kmeans quality vs data
The estimation quality of the mean improves with sqrt(n).

So with more and more data, your mean will get more precise. But the improvements get slower and slower.

It won't help with all the other issues of k-means, such as problems with different cluster diameters and outliers. And more data probably means more outliers...

You can try a similar approach to that paper with k-means with some slight modifications. Try plotting the sum of squared deviations between the holdout set, and the nearest centroid each. As long as this improves, the clusters fit your holdout set better.