To be sure you have no additional tracking software installed, you may use these 3 methods.
Method 1
Check logged Google accounts Settings -> Accounts: be sure to use only your account for all Google products/services (Play Store, Maps, Android Phone Manager - this one can track devices). To be 100% sure, only you are the administrator of your phone, set up a new Google account for yourself.
In Settings -> Security -> Device Administrators, check programs set as admins -> remove all if there are any. (If you find one PIN-protected, use Method 2 with hard/factory reset.)
Remove all additional apps that may be used for tracking Settings -> Apps -> Downloaded - select and remove all, one by one (some might be PIN-protected, then go to Method 2).
In Settings -> Location Services, disable the Access my location option and turn off GPS.
Disable Mobile data transfer.
Set up and enable PIN and Password (Settings -> Security), and enable screen protection with a PIN number.
Method 2
Manually back up your data (music, pictures) and copy it with file explorer/manager onto an SD card. SMS can be backed up with SMS Backup + App, sync contacts with Google Account. (for security reasons, set yourself a new fresh one and use it to back up and restore your data.)
Then, go to Settings -> Backup and Reset, choose Factory Data Reset important - uncheck Automatic Restore checkbox. After a hard reset, choose your own new Google account for Google services (set up a new one).
Next, set up and enable Password (Settings -> Security), and enable screen protection with PIN.
Additional info
Apps that can track your phone
- Google Device Manager
- Kaspersky Mobile Security (This one is tricky and hard to erase. I use this one with my phone.)
- Avast Mobile Security / Avast Anti-Theft (This one sends an email notification or SMS when the phone leaves the designated area. It also may be hard to remove. You will need a hard reset to get rid of these two). Anti-Theft hides itself as an update agent in apps.
- Track My Phone
- Phone Locator
...and many many more. Check them in Google Play (You may find one installed on your phone. If so, remove it.)
Method 3 (100% works)
Buy another cheap smartphone and a second SIM card. Install on this new phone, let's call it decoy, the software they have installed on your old phone for tracking you (you will find it in Settings -> Apps on your Galaxy), log them in, put it into that second phone your old SIM card, redirect all phone calls to you a new number which you will use with your factory erased / clean Galaxy with new accounts logged in. Leave the second (decoy) phone in a place you are supposed to be.
If you can't find the app which they are using to track you down or don't have passwords to log them on a second phone, use the reverse process: buy yourself another phone with a new number (can be prepaid) and redirect all calls onto the new one from your old SIM card and use the old phone as a decoy.