Mystery application called "Add Contacts" After a factory reset there is no application present on the phone that is called Add Contacts. On such a clean unit I used Google Play Store to install Skype. I think Google Play Store requires some sort of update so I allowed that update to be installed. I don't remember exactly what the update was called but it seems to always be a requirement after a factory reset upon the first use of the Play Store so it is probably a legitimate Google update.

After using this fairly "clean" unit for very little time a new application called Add Contacts appeared in the "wallpaper" array of applications. It asks for permission to read my location. 

Is the "Add Contacts" program malware? What caused this to be installed?

I did another factory reset to get rid of it. Note that under the Backup &amp; reset function is a  Backup &amp; restore dialog with the check box for back up my data and a check box for automatic restore. I UNCHECKED both before doing the factory reset. After the factory reset I also UNCHECK both before connecting to WiFi. I next used Google Play Store (allowing the mandatory update related to the use of Play Store) to install Skype (non-advertising version) and nothing more.

This unit has Android 4.4.2.

Update: It has been about 3 weeks since the last factory reset. A few hours ago I noticed that the Add Contacts icon is on the wallpaper array of applications. I did another factory reset. I will install Skype (non-advertising version). I also installed that update that Google requires before allowing the use of Play Store. (I need Play Store to install Skype and for no other reason.) As an experiment I will use only the native SMS application, voice calls, and Skype. For the past 3 weeks I have not used any other application but to be sure I will un-install several of the default applications just to increase my confidence that nothing is being invoked that I cannot account for. I have instructed people never to send photos or other attachments to my Skype and the default SMS application and I made a mental note to myself never to use the camera and to never use service provider data other than SMS. This phone will only ever process WiFi data and only for Skype. I will monitor for the mysterious appearance of applications or other unexpected behaviour.

Update: The "Add Contacts" application reappeared after only a few hours. I will do another factory reset with backup my data disabled and automatic restore disabled. The application "Add Contacts" version 3.0 has the following permissions: read phone status and identity, precise location, read contacts, modify or delete SD card, read SD card, disable screen lock, view WiFi connections, full network access, run at startup, retrieve running apps, draw over other apps, modify system settings, and many more. There is no app by the name "Add Contacts" in the Play store. After a factory reset I immediately disabled backup my data and automatic restore before enabling WiFi. This time I was able to use the Play store and install Skype and there was no prompt to do an update to Google Play "services". This is unlike before and perhaps strange. As always, there will be no deliberate use of service provider data other than SMS. All data use will be through Skype and WiFi. Voice calls and SMS will be handled with the default Android features. There will be no use of the camera and there will be no receipt of attachments via Skype and SMS. People have been instructed not to send me attachments. Play store will not be used to install anything other than Skype.
There is sometimes an Add Contacts app that comes with Android. With the newer versions of Android, the add contacts button is in the Contacts app. So it is NOT malware.