We investigate the physical mechanisms underlying the spreading of entanglement in a quantum many-body system following an abrupt change of one of its control parameters --a quench. In particular, we focus on extended systems where the interaction among the microscopic building blocks decays as a power-law 1 / r^{alpha} at long distance. The buildup of correlations and entanglement in these systems has been studied a lot recently, mainly in connection with the breakdown of Lieb-Robinson bounds for sufficiently small alpha, and very paradoxical observations have been reported, for which no physical explanation has been put forward : while long-range interactions enable distant subsystems to become essentially instantaneously correlated, the growth of entanglement entropy in a subsystem is rather slowed down by long-range interactions. In this work, we propose a scenario resolving this paradox. We argue that the growth of entanglement entropy is a relaxation process involving time scales ranging from zero (for the fast modes) to infinity (for the slow modes), corresponding to the divergency of the velocity of the fastest quasiparticles for sufficiently long-range interactions. We support this scenario by analytical and numerical calculations on the long-range XY spin model.