The water in equilibrium with ice will be 0 degrees. The ice could be -20.

The brine mixture can indeed be colder, and the water is the bit that's in contact with the fish, so that's important.

It may be that the very cold ice on top of the water loses more heat to the environment more quickly than an even temperatured slurry. There might be a higher temperature gradient between that ice and outside than between the brine slurry and outside, which may mean slower warming overall for the slurry.