Wonder if it's written itself into recovery. Or the SIM card/baseband - SIM card in particular usually includes functionality for triggering a sideload of apps (eg for carrier apps), sending notifications, etc into the main SOC so it fits. Maybe the second instance of SIM card malware ever.
https://www.youtube.com/watch?v=31D94QOo2gY
There are only so many places it can be hiding if it's surviving a factory reset.
--Guy who is undoubtedly vastly underestimating the problem given that it's resisted AV vendors for a while