We measure a relation between the depth of four prominent rest-UV absorption complexes and metallicity for local galaxies and verify it up to z~3. We then apply this relation to a sample of 224 galaxies at 3.5 < z < 6.0 ( = 4.8) in COSMOS, for which unique UV spectra from DEIMOS and accurate stellar masses from SPLASH are available. The average galaxy population at z~5 and log(M/Msun) > 9 is characterized by 0.3-0.4 dex (in units of 12+log(O/H)) lower metallicities than at z~2, but comparable to z~3.5. We find galaxies with weak/no Ly-alpha emission to have metallicities comparable to z~2 galaxies and therefore may represent an evolved sub-population of z~5 galaxies. We find a correlation between metallicity and dust in good agreement with local galaxies and an inverse trend between metallicity and star-formation rate (SFR) consistent with observations at z~2. The relation between stellar mass and metallicity (MZ relation) is similar to z~3.5, however, there are indications of it being slightly shallower, in particular for the young, Ly-alpha emitting galaxies. We show that, within a "bathtub" approach, a shallower MZ relation is expected in the case of a fast (exponential) build-up of stellar mass with an e-folding time of 100-200 Myr. Due to this fast evolution, the process of dust production and metal enrichment as a function of mass could be more stochastic in the first billion years of galaxy formation compared to later times.