eodman has posted a link to a news article which, I think, answers many of your questions, but I believe historically, we can conclude that the ocean fish stocks were relatively stable up until the modern era of "industrial fishing". So I don't see that it would be necessary to have done a comprehensive count of the ocean's fish - we know how much fish was being caught 40 years ago, we know how much fish is being caught today, we can draw reasonable conclusions.

And the notion that the only way to count a group of something is to assign a number to every single member of the species is just wrong. Scientists have been using sampling techniques for over a hundred years to estimate numbers of things that are too many to count, and fish populations are no exception. In any event, I don't need to know how many fish there are now, or how many there were then, to be able to estimate that there used to be ten times as many as there are now.