The first thing you should do is uninstall CleanMyMac according to the developer's instructions. It is considered to be akin to malware by most users here.
You can check to see if you've removed all of the files by downloading and running Find Any File to search for any files with the application's name and the developer's name in the file name. For example for CleanMyMac software you'd do the following searches:
1 - Name contains cleanmymac
2 - Names contains macpaw
Any files that are found can be dragged from the search results window to the Desktop or Trash bin in the Dock for deletion.
FAF can search areas that Spotlight can't like invisible folders, system folders and packages.
Also don't use the About This Mac Storage graphics to determine free space on your drive. Control (right) - click on the drive's icon and select Get Info from the contextual menu. What you'll find in the Info pane is an accurate depiction capacity, amount used and the amount of free space. The same goes for any folder on the hard drive.
If after deleting a lot of files you don't see the change in the Info pane you should reindex the hard drive for Spotlight: How to rebuild the Spotlight index on your Mac - Apple Support
