late 14c., "a portion or part of something" (a sense preserved in the verb and in the phrase parcel of land, which is from c. 1400), from Old French parcele "small piece, particle, parcel," and directly from Medieval Latin parcella, from Vulgar Latin *particella, extended form (via a diminutive suffix, but not necessarily implying smallness) of Latin particula "small part, little bit," itself a diminutive of pars (genitive partis) "a part, piece, fraction" (from PIE root *pere- (2) "to grant, allot").
Meaning "a package" is recorded from 1640s from the earlier sense of "a quantity of goods in a package" (mid-15c.), which is from the late 14c. sense of "an amount or quantity of anything." The expression part and parcel (early 15c.) also preserves the older sense; both words mean the same, the multiplicity is for emphasis. In some old and technical senses, parcel is used as an adjective or adverb meaning "in part, partially, to some degree." Parcel post as a service to deliver packages (later a branch of the postal service) is by 1790.
"to divide into small portions," early 15c., parcelen (with out), from parcel (n.). Related: Parceled; parcelled; parceling; parcelling.