I had the same problem, it kept me busy for a week or so, but after investigating my complete setup i found the following:
Within my ASP.NET application, i had an image directory and an image cache directory, with lots of images in them. (+200.000). Both were not included in my VS project, but still Visual Studio / TFS tripped over this.
First i found, that when checking in some files (which took over 10 minutes when the problem existed), in 'Team Explorer - Pending Changes', under 'Excluded Changes' it said: 'Detected: 50000 add(s)'.
Trying to get rid of this the 'normal way', by opening that 'Promote Candidate Changes' window and setting these files to be ignored, still didn't do much.
But after moving those image directories to some other location, outside my project, all problems disappeared.
Of course i had to add those moved directories as virtual directories to still see my images.