First off, incredible pixel art and lovely colour palette. Really adds to the relaxed mood of the game.
I wasn't sold on the concept of having to catch the same fish twice, but it grew on me as I played and the crux of the mechanic became more clear. Though I think there's some tedium that adds a bit of annoyance to the experience. Specifically, when you snag a fish, you have to manually reel it back in really slowly; this especially tedious if you're hunting real deep for swordfish and the like. Having some kind of quick reel (since there's no mistakes that can be made or skills that have to be exerted) could solve that.
Also, the UI tells you the name of the last fish you caught, but it feels like it would be more useful to show an image so I can pick the right one. Most are pretty obvious (e.g. the swordfish and crab), but e.g. I at one point forgot which of the two little fish I'd caught, damsel or butterfly. Having a picture there would have helped.
Anyway, great game!