I agree w knight, software like that (either on PC or android, in this case) tends to try and embed itself. If you are rooted, I would:
make a nandroid backup via your recovery of choice(just in case, bc having a backup never hurts)
Copy all data on internal storage to a PC
Wipe system, Data, caches, internal storage x2 just to be sure
And reinstall your ROM of choice.
Formatting storage may not be needed, but I know I keep a lot of personal info (banking, work info and such) on my device so I would make totally sure that bad software didn't try and leave any nasty traces.
At the very least, wipe system, data and caches then reinstall your ROM.
*Edit* also, some apps like titanium backup and some file explorers let you force remove apps and their associated files. Maybe look into one of those before totally wiping.
Good luck and best wishes man, that seems like a wretched app/malware (IMO)
Sent from my Nexus 5 using Xparent Skyblue Tapatalk 2