Swimming Baths (Victoria Recreation Club) [1866-1900]
The location is approximate, based on the 1880 map of the area (the baths are out in the water, below the caption "North Barracks"):
The baths were completed in 1866, as noted by Adam:
More substantial articles on the pool itself can be found in the June 6 (planning) and October 26 (pre-opening) editions of the Daily Press for 1866.
They were destroyed by the 1874 typhoon (see the newspaper print below), and re-built.
Though described as "public baths", Adam notes:
There's a letter, appparently from an Indian writer, bemoaning the admission policy in the March 17, 1870 edition of the Daily Press.
And the China Mail's editorial for 19 Sep 1892 shows that most of Hong Kong's population wouldn't have been able to swim there:
To those who do not feel a sufficient interest in Aquatics to care much whether proper facilities for this form of healthy exercise exist or not, the subject may appear to be one in which neither the government nor the public are called upon to interest themselves, and which ought to be left entirely to the members of the Victoria Recreation Club. It must be remembered, however, that hitherto this small enclosure near Murray Wharf has been the only thing in the shape of a public path of which the colony could boast. It has always been as much open to the public as any institution that could be called a "public bath" could prudently be made in this colony, in as much as it might be said to be accessible to any respectable member of the non-Asiatic population on payment of the very moderate fee of $10 per annum.
I've set the demolition date to 1900, but it's a guess - in any case, around the time of the big reclamation here.
If you can add any more information, please let us know in the comments below.