It's a common problem. Here's what happens. Disk cleanup in it's stock form will make a test run of "compress old files." This is CPU intensive and many older Pentium 4 laptops will overheat and reboot on this step.
Fix? Fix the laptop. Have the CPU Heatsink and Fan cleaned (many never maintain their units), and in some cases the heatsink needs to be reattached. A laptop cooling pad sometimes helps.
Everytime I use Disk Cleanup, it goes 1/4 way then my laptop restarts by itself?? Anyone know why?? I have Window 2000 Pro SP 4.