Mail looks like the worst business in the game: even if I put mail stops connected with the biggest factories (high level of mailing) the amount of the mail delivered is ridicolous and the loss enormous; does anybody know how to make a profitable mail business? It's the only one that seems impossible to make money with...
Mail is different from other goods, similar to passengers. Usually just a point-to-point connection does not work for these two - you need an extensive network that allows people from more or less all houses in a major citiy, to reach more or less all houses in other major cities. In other words: just make sure that the coverage area of your passenger network's (including small local bus or tram lines) stops cover most of the area of your cities.
Mail should follow the same principle - just in smaller numbers.
INdeed you need a extensive network, similar as for passengers but with much smaller numbers: The amount of mail generated is about 1/3-1/4 of the same number of passengers (with the exeption of attractions, that should put 8x more mail outward than inward).