While reformatting will work, it's a rather extreme solution which I think most people would like to use only as a last resort. Things you can try before:
Most antivirus makers also have boot CDs. You can boot from this and use it to run your virus scan. The virus/malware won't have its clutches on the OS from boot-up.
You can remove the hard drive, place it in a computer you know is clean (you can mount it directly inside the case, or via a USB 3.0 enclosure), and run the anti-virus and malware scans from the second computer. I don't think Malwarebytes has a boot CD, so this is about the only way to run it if the malware is preventing Malwarebytes from functioning.
Depending on how deeply the malware has embedded itself into...