We explore the evolution of the Colour-Magnitude Relation (CMR) and Luminosity Function (LF) at 0.4<z<1.3 from the VIMOS Public Extragalactic Redshift Survey (VIPERS) using ~45,000 galaxies with precise spectroscopic redshifts down to i_AB<22.5 over ~10.32 deg^2 in two fields. From z=0.5 to z=1.3 the LF and CMR are well defined for different galaxy populations and M^*_B evolves by ~1.04(1.09)+/-0.06(0.10) mag for the total (red) galaxy sample. We compare different criteria for selecting early-type galaxies (ETGs): (1) fixed cut in rest-frame (U-V) colours, (2) evolving cut in (U-V) colours, (3) rest-frame (NUV-r)-(r-K) colour selection, and (4) SED classification. Regardless of the method we measure a consistent evolution of the red-sequence (RS). Between 0.4<z<1.3 we find a moderate evolution of the RS intercept of Delta(U-V)=0.28+/-0.14 mag, favouring exponentially declining star formation (SF) histories with SF truncation at 1.7<=z<=2.3. Together with the rise in the ETG number density by 0.64 dex since z=1, this suggests a rapid build-up of massive galaxies (M>10^11 M_sun) and expeditious RS formation over a short period of ~1.5 Gyr starting before z=1. This is supported by the detection of ongoing SF in ETGs at 0.9<z<1.0, in contrast with the quiescent red stellar populations of ETGs at 0.5<z<0.6. There is an increase in the observed CMR scatter with redshift, two times larger than in galaxy clusters and at variance with theoretical models. We discuss possible physical mechanisms that support the observed evolution of the red galaxy population. Our findings point out that massive galaxies have experienced a sharp SF quenching at z~1 with only limited additional merging. In contrast, less-massive galaxies experience a mix of SF truncation and minor mergers which build-up the low- and intermediate-mass end of the CMR.