As a non-epidemiologist, it's hard to say, but it could well have been pretty devastating. A reasonable comparable disease might be syphilis, since that's spread in broadly the same way, and it this was rather common in the 19th Century (at least in Europe), then so too might HIV have been. In which case "pretty devastating" would be a fairly accurate description; more so, as HIV is a viral disease whereas syphilis is bacterial, so that anything based on antibiotics would be useless at treating it.
At a rough guess, it would likely be equivalent in scope to Black Death, but it's hard to say as there are so many suppositions, such as: would the disease again develop firstly in Africa?