"post, letters," c. 1200, "a traveling bag, sack for keeping small articles of personal property," a sense now obsolete, from Old French male "wallet, bag, bundle," from Frankish *malha or some other Germanic source, from Proto-Germanic *malho- (source also of Old High German malaha "wallet, bag," Middle Dutch male "bag"), from PIE *molko- "skin, bag."
The sense was extended to "bag full of letters" (1650s; perhaps via phrases such as a mail of letters, 1654) and "person or vehicle that carries postal matter" (1650s). From thence, to "letters and parcels" generally (1680s) and "the system of transmission by public post" (1690s).
As a newspaper name, by 1789. In 19c. England, mail was letters going abroad, while home dispatches were post. Sense of "a personal batch of letters" is from 1844, originally American English. Mail slot "narrow opening in an exterior door of a building to receive mail delivery" is by 1893, American English. OED defines it as a "letter-slit."