Why does the US Postal Service have mailmen, but the Royal Mail has postmen? 
For the same reason that mail trucks drive on parkways and park on driveways.
[sub]I have heard both “mailman” and “postman” used in the US. Officially, they are “mail carriers.”[/sub]
Because the English language in the US (when mail/post delivery was starting out and the post office was just a thought) was influenced by more than one culture, whereas ‘post’ was decidedly more English. “Mail” has and ‘‘old French’’ origin.
And this: Etymology
The word mail comes from the Medieval English word male (spelled that way until the 17th century), which was the term used to describe a traveling bag or pack.[13] The French have a similar word, malle for a trunk or large box, and mála is the Irish for a bag. In the 17th century the word mail began to appear as a reference for a bag that contained letters: “bag full of letter” (1654). Over the next hundred years the word mail began to be applied strictly to the letters themselves, and the sack as the mailbag. In the 19th century the British usually referred to mail as being letters that were being sent abroad (i.e. on a ship), and post as letters that were for localized delivery; in the UK the Royal Mail delivers the post, while in the USA the US Postal Service delivers the mail. The term e-mail (short for “electronic mail”) first appeared in 1982. The term snail-mail is a retronym that originated in 1983 to distinguish it from the quicker e-mail.
–Wikipedia
In Canada, they’re “letter carriers”. And it’s “Canada Post”, but I’m sure I’ve seen “Royal Mail” on old letter boxes (the kind that are bronze flaps next to old downtown post offices)
The gender neutral term in the U.S. is “mail carrier.” Were letter carriers previously called lettermen?
Yes: in those days before they even got the job lettermen had to prove they were faster than a rolling O and stronger than Silent E.
Probably too obscure: the reference.
It’s letter carrier in the US too. Their union is the NALC (National Association of Letter Carriers)
Royal Mail is the brand that the letter-carrying division of the Post Office has adopted in recent years (they tried calling themselves ‘Consignia’ for a while, which everyone told them was just dumb, and eventually they dropped it). The actual ‘post office’ bit where you went to buy stamps was called Post Office Counters Ltd. All of it used to be a government department called the General Post Office; the Post Office Engineering Dept. ran the telephone service.
Postmen. I think they wanted to get away from using the term ‘men’ in the word.