But that implies that when work is done with no heat flow (i.e. reversible adiabatic expansion), the entropy of the system doesn't change.
Reversible processes are by definition the processes which doesn't generate entropy - otherwise they would not be reversible. In fact, a process occurring at finite speed necessarily involves generation of entropy, but from the point of view of thermodynamics a process can be always made slow enough for this change to be negligible.
We identify the first partial with temperature, and the second with (negative) pressure.
The logic goes in the opposite way: the energy of a closed system is conserved. In thermo/stat. physics we assume that this energy can be changed in two ways: via macroscopic changes, which we call work and on a microscopic level, which we call heat, that is
$$
dU=dQ - dW.
$$
Work can be performed in many different ways - by changing the system volume, by changing magnetic field, etc. So generally we write:
$$
dW = \sum_i x_i dX_i
$$
$pdV$ is just the most common type of work encountered when dealing with gases, which is used throughout statistics physics textbooks for illustrative purposes, as well as for historical reasons (when Sadi Carnot had in mind real steam engines, even though his results are applicable to nuclear reactors.)
Entropy as an adjoint variable to temperature was defined by Clausius as (see this answer for alternative entropy definitions):
$$
dS = \frac{\delta Q_{rev}}{T}
$$
Now we have
$$
dU = TdS - pdV,
$$
and, since $U$ is a function of state, i.e., it is unique for any combination of variables $S, V$, we have to identify the pre-factors as the partial derivatives:
$$
T=\frac{\partial U}{\partial T},p=-\frac{\partial U}{\partial V}.
$$
(For more variables we would also have $x_i=\frac{\partial U}{\partial X_i}$, see also this answer for a crash course on differentials.)
We have a gas, let's say, that is expanding in such a way that the pressure against it always matches its own pressure. It therefore loses energy as it expands, which tends to decrease its entropy, but it gains entropy due to the increase in volume, and somehow these two effects perfectly cancel out!
(emphasis is mine)
It is not clear where the intuition behind the statements in bold comes from (that decrease in energy should cause change in entropy or that change in volume should increase entropy) - this does not follow from the equations discussed above. Rather, such an expansion corresponds to changing the energy along the path with $dS=0$: as energy is a function of multiple variables there are different paths connecting two energy values (imagine the image below in variables $S,T$, image source):
