OK ... so ... Here's what I did recently when I got my S6. First, a little background info:
Way back when, I was on a blackberry I inherited from my father. He didn't clean it off before giving it to me, and he had a lot of contacts of business people and family friends that I didn't already have, so I left them in there. I then added my own contacts. Then, later, I changed to an iPhone ... and was working at a large firm. So, I had exported all our company contacts to a file, and imported them in Outlook on my personal PC. I then sync'd that to my iPhone. So on and so forth, with a few more companies, more personal contacts, etc. I ended up with over 3000 contacts, lots of which I didn't even know if they were current, and lots of others that I realized I just didn't need at all.
So when switching to my S6 ... I wanted to clean up my contact list, but our new phones don't sync well with Outlook, so I decided to just bite the bullet and move all my contacts over to Google.
Long story short ... what you need to do is use whatever means necessary to export your contacts to CSV files, and then import into your Google contacts. Once you get them all there, you can have Google pull up a lost of "duplicate contacts". From there, you need to review those duplicates and merge any info you want to combine. I honestly don't recall if Google Contacts can do this automatically, or if you have to do it manually. But either way, you can get it done.
Once you have that done, then go into your phone's contact list settings, and tell it to ONLY show contacts from Google ... and you will finally have a cohesive list of contacts, with no duplicates.
From here on out, just either add new contacts in your phone (making sure to assign it to the your google account - and not to your phone, or any other email addresses or accounts you have on your phone) ... or you can go directly to the google contacts portion of your google account on your pc, and add the contacts there. If you have contact syncing set up with your phone, as soon as you add or edit a contact in either location, the OTHER location will show it as well ... it's just one list, and you're only added/deleting/editing from your device or pc ... its kinda like your IMAP email account, but with contacts.
It's pretty nice now that I have it all setup ... Give it a try ... it might take a little time, but once you get it done it will be smooth sailing.