2nd Gen Surfing?

I recently got the HM Surf, but when I checked Bulbapedia to see what Pokemon are located in different water areas that could be obtained by using Surf, only Fishing was listed, even though Gen 2 had Surf listed.

In Gen 1, was it possible to find Pokemon in water by using surf?

Yes it was possible, I'm seeing a section for surfing on route 20.
Perhaps you were looking at an area specifically didn't have any pokemon that could be found surfing.

I recall when I played Blue, whenever I was surfing on Routes 19, 20, and 21, I had to keep an eye out for Tentacool.

The only map that I can think of that didn't have data for surfing pokemon is cinnabar island.
But yes, you can encounter pokemon via surfing

Most of the water routes you surf through have encounters. Tentacool being the most prolific of course. I recall there were quite a few cool Pokemon you could find in the route (I forget its #) near Whirl Islands.