ref
mail + man
mailman (n.)
also mail-man, "person employed in carrying the mail over a specific route or between post offices," 1841, from mail (n.1) + man (n.). Mail-carrier in the same sense is from 1799.