you are asking a very good question and obviously labeling 4,000 files should not take more than twenty minutes in most environments. Still, I have seen this problem before and can suggest a few things to consider.
The first is to check the health and integrity of the vob itself. You should be using commands like cleartool checkvob among others on a nightly basis to verify the integrity of the vob. You should also look at how the vobs are being accessed. If you run cleartool lsvob and lsview then you can look at the location of vob and view storage area respectively. You need to verify that the storage areas are accessible and working correctly. In one instance, I found that the vob was being hosted on a NAS device that was not configured correctly (e.g. CIFs) and the problem actually was not related to clearcase and theproblem was also seen while storing any files on the NAS from unix. Another issue that I have seen is where the view storage area was located remotely - and actually turned out to be on a desktop in London while the user was in NYC! Yikes!
Are other users having the trouble? Did you stop and restart the Clearcase processes? Did you check the logs for related messages? How big is the vob in terms of space? You might have only 4,000 files that you can see but maybe the vob is bigger than you realize. You should compare the vobs that have better performance with the one that is misbehaving. One more thing to check and its a classic issue - is anyone running triggers against the vob that could be firing off on labeling (causing asynchronous activity and slowing down your server). I don't usually see this on mklabel though.
Do give us a little more information and I will tweet this out to our readers for their comments!
Bob Aiello, Technical Editor CM Crossroads