Advice on securely removing malware
Malwarebytes is at best terribly ineffective from my experience. Why do you suspect a rootkit? I don't think you're wrong, possibly very perceptive but just wondering why. 

The problem with rootkits is they will hide all evidence of their existence especially from a rickety Malwarebytes scan. Mac malware creators must be sophisticated enough to jump some of the small hurdles Apple attempts to create so keep that in mind in terms of the persistence factor at play. 

What makes you think that the malware won't go hide in your NVRAM, xartstorage (secure enclave, graphics card, SMC, create a RAMDisk, etc. to make you think that it's gone and that Recovery Mode really is an almighty kill switch and isn't just a pacifier that effectively negates all legitimate and acceptable levels suspicion.

macOS (previously styled OS X) is inherently insecure. "It just works" is not the befitting of a truly secure operating system. In which case "I expletive hate it," would probably be more likely. Focus groups probably would have found that didn't go have quite the same cachet. 

To assess the potential of this type of malware: 


Open terminal and type cat /dev/ and paste the results if you wish. 
When you reinstall the OS in Recovery, look for an process called "unknown" the the install logs (Command L and then be sure to select the option in the top left corner to show all progress and errors). 
You could also enable kernel debugging and read the kextlog shown as your OS boots. In full disclosure this does require a high level of modest effort so it's perfectly acceptable and possibly most productive to dismiss the possibility of a root-kit in advance.
Obtain a copy of the entire disk with all volumes and mount it read only to a Windows VM then try various malware scans.