I’m not sure that the question is well-formed. The energy we take away from the tides is the kinetic energy of the water as we reduce its movement. The law of conservation is preserved.
If the question is about where the water’s kinetic energy is coming from, then I don’t think tidal power is a necessary part of the explanation. In that case, the question is basically how does gravity work? That is, the problem is that gravitation is a force that seems to create energy in the form of tides. We know energy can’t be created, so when water gains energy in the form of tides, what is losing energy?
That’s an interesting problem, and here‘s a physics forum dealing with it in ways that I don’t quite understand. Their answer is that due to gravity, “Earth’s rotation is slowing, and the moon is actually being raised into a higher orbit around the earth” (over a very, very long period of time). That means that the moon’s orbit around the earth transforms (via gravity) the kinetic energy of the Earth’s rotation into tidal movement.
However, if we harness tidal energy, we’re not increasing the amount of gravitation between the moon and the earth, so we won’t slow the earth any more quickly. Gravity is going to exist regardless; using tidal energy will just mean that on our end the energy created by gravitation will be used as electricity rather than water movement.