Yes that is exactly correct. I would suggest using VBA to find the palette and then just changing the colors accordingly. I personally like the more blue underwater anyways

To my understanding, in the game only 16 palettes are available for use in the tiles. Another way you could do this is to change a palette that is not being used. I did this to add in a lava section to one of my maps. In this case, I used palette 7 to change some of the unused pink to red. Otherwise just stick to using palette 6 which is all blues (Icefall Cave uses this palette I believe)
Check out the colors in this palette

Good luck!