Although the terms are often used interchangeably, they have slightly different meanings.
Erythrocytosis is an increase in red blood cells (RBCs) relative to the volume of blood. Primary erythrocytosis is associated with an elevated red cell mass (a change in the numerator in RBC/volume), while relative erythrocytosis is not (rather, it is a change in the denominator in RBC/volume). An important caveat is that an increased number of microcytic RBCs, for example in thalassemia, may be associated with a normal or even low red cell mass (Hct=MVC x RBC count). Indeed, before its cause was known thalassemia was historically referred to as microcytic erythrocytosis.
Polycythemia refers to increased red cell mass, manifested by increased Hct and/or hemoglobin, and usually caused by increased RBC count (erythrocytosis). In theory, an elevated MCV could produce increased red cell mass independent of RBC number (Hct=MVC x RBC count). As the name ‘poly’ implies, polycythemia more accurately refers to pan-myeloproliferation, but this definition is not normally adhered to.