I know it only be reputation, but I'm pretty sure the film you reference is Amphibian Man (Человеκ-aмфибия) based on a book by the same name; "The Sea Devil" was the hit song from it.
From the sound of it to me, and I haven't see it either, The Shape of Water is one part Amphibian Man, one part Creature of the Black Lagoon (or more specifically, Revenge of the Creature where the Creature falls for a girl, albeit with less romantic results).