Personally I think the cleanup process can help reduce the sizes but not really sure how much you can reduce considering the sizes of those dbs.
That being said, when you execute the cleanup databases command what will happen is that Sitecore will get the list of databases you select on the dialog and add them to a cleaner job that will get executed.
You should see logs on Audit mode(if you don't have it you can always set them on log4net).
Now back to your original problem(db sizes) one thing I would suggest you to do is run a powershell script to get things like unused items, unused media items(this can be a cause for big dbs - hugh media library), etc.
This can pinpoint a few things on your build that can be improved.
One last thing: I remember that the last time I had to deal with Sitecore 6.5 versions I was using Chrome and some of Sitecore's features were not working with newer Chrome versions. Not sure if that's the case for you but if you are using Chrome I'd suggest you to try in the old Internet Explorer to trigger them just in case. That would explain why clicking on the cleanup databases link and nothing showing up on the logs.