I had the same issue, restored my S6 from a backup of my S5. ECG app nowhere to be found. Unpaired, re-paired, many many times, no dice. Decided to set up my S5 again and it also no longer had the ECG app. Called Apple, and they had me unpair and re-pair a few times, then wanted me to wipe my phone (I told them I wasn't going to do that). They said someone would get back to me within a week. The next day I got a call from someone who said they were with the Health Team (I don't think that was the official name, all I heard was "Health" something or another).
He sent me a link via email for a Health Support app, and it installed on my phone and watch. He had me open it, enter the case number he provided, and then he said it'd ask me a few questions and then send them diagnostics. It got to the part where it asked to me hold the crown and power button and wait for a vibrating pulse.
I ended up holding it too long, which of course force reset/rebooted the watch. When it came back on (took about two minutes to reboot), he had me open the Health Support app again to run the tests again -- before I did I opened the Health app and immediately was asked to setup the ECG app (it wasn't there at all before, only the results from previous tests were present in the Health app).
He said it was possible that the force reboot/restart cleared something out and that made things synch back up, and that I didn't need to continue with log submissions. He did mention at the start of the call that he'd had other calls about this, but never discussed if they got theirs working or not. In my case I think I just got lucky, as I posted in another thread on here of someone else having the issue, and the force reboot/restart didn't seem to fix it for them.
I suggest calling Apple and getting things rolling so they can see what's going on, as this is one of the features that a large number of people got the watch for to begin with, and having it disabled/removed by upgrading to a newer watch makes zero sense.
Good luck!