Second Law of Thermodynamics:
Postulate of Kelvin:
A transformation whose only final result is to transform into work, heat extracted from a source which is at the same temperature throughout the process is impossible.
Postulate of Clausius:
A transformation whose only final result is to transfer heat from a body at a given temperature to a body at a higher temperature is impossible.
These statements are both equivalent to each other and states what we call the Second Law of Thermodynamics.
The Carnot efficiency is given by
$$\eta = 1-\frac{Q_1}{Q_2}$$
where
\begin{align}Q_2 &= \textrm{Thermal energy absorbed by the system from a source }~ t_2,\\ -Q_1 &= \textrm{Thermal energy absorbed by the system from a source }~ t_1,\\ t_2 &\gt t_1\;.\end{align}
For any other non-reversible engine ($'$) operating between the same temperatures $t_1$ and $t_2$, the efficiency of the same can never exceed the efficiency of a reversible cyclic (Carnot) engine:
$$1-\frac{Q_1}{Q_2}\geq 1-\frac{Q'_1}{Q'_2}$$
Since, $Q_2/Q_1$ depends only on the temperatures of the source, the ratio can be expressed as
$$\frac{Q_2}{Q_1}= f(t_1,t_2)\;.$$
Suppose, a reversible engine operates between $t_0$ and $t_1;$ then $$\frac{Q_1}{Q_0}= f(t_0,t_1)\tag{I.a}$$
Let another reversible cyclic engine operates between $t_0$ and $t_2;$ we have
$$\frac{Q_2}{Q_0}= f(t_0,t_2)\tag {I.b}$$
Dividing $\rm (I.b)$ by $\rm (I.a),$ we get $$\frac{Q_2}{Q_1}= f(t_1, t_2) = \frac{f(t_0,t_2)}{f(t_0,t_1)}\;.\tag I$$
$t_0$ is arbitrary and can be taken constant; therefore, $f(t_0,t)$ only depends on $t$. So,
$$f(t_0,t) \equiv \mathrm K'~\theta(t)\;.$$
So, $$\frac{Q_2}{Q_1}= f(t_1, t_2) = \frac{f(t_0,t_2)}{f(t_0,t_1)} = \frac{\theta(t_2)}{\theta(t_1)}\;.$$
Since, $\theta$ is not unique, we can freely choose its unit: the scale can be chosen based on the difference of boiling point and freezing point of water at one atmosphere pressure.
This new scale $\theta$ can be showed to coincide with the absolute temperature scale $T\;.$
So, we have $$\frac{Q_2}{Q_1}= \frac{T_2}{T_1}\tag{I.i}$$
For any system working between the sources $T_1, T_2, T_3,\ldots, T_n$ with the interacted thermal energy as $Q_1, Q_2, Q_3,\ldots,Q_n$, the following is always true during a cyclic transformation:
$$\sum_{i=1}^n \frac{Q_i}{T_i}\leq 0\tag{II} $$
In case of continuum of sources, the summation becomes
$$\oint \frac{đQ_\textrm{system}}{T_\textrm{source}}\leq 0\tag {II.a}$$
This is the celebrated Clauisus Inequality which is a re-statement of the Second Law of Thermodynamics.
Note, $T$ in the denominator is not that of system; it's of the source - the reservoir.
However, $$T_\textrm{source} = T_\textrm{system} ~\iff ~\textrm{reversible cycle}$$ and $$\oint \frac{đQ_\textrm{system}}{T_\textrm{system}} = 0\tag{II.a.i}$$
Entropy and the Second Law:
Let $\rm A$ and $\rm B$ be two equilibrium states of a system.
Consider two reversible continuous curves connecting $\rm A$ and $\rm B$ viz. $\mathtt I$ and $\mathtt I';$ together they constitute a reversible cycle. So, applying $\rm(II.a.i)$ we have
\begin{align} \oint_{\mathrm A \mathtt I \mathrm B \mathtt{I'}\mathrm A } \frac{đQ_\textrm{sys}}{T_\textrm{sys}} & = 0 \\ \implies \left (\int_{\mathrm A}^{\mathrm B} \frac{đQ}{T}\right)_{\mathtt I} + \left (\int_{\mathrm B}^{\mathrm A} \frac{đQ}{T}\right)_{\mathtt {I'}} & = 0\\ \implies \left (\int_{\mathrm A}^{\mathrm B} \frac{đQ}{T}\right)_{\mathtt I}- \left (\int_{\mathrm A}^{\mathrm B} \frac{đQ}{T}\right)_{\mathtt {I'}} & = 0,\end{align} which implies $$\left (\int_{\mathrm A}^{\mathrm B} \frac{đQ}{T}\right)_{\mathtt I} = \left (\int_{\mathrm A}^{\mathrm B} \frac{đQ}{T}\right)_{\mathtt {I'}}\;.\tag{III}$$
Now, this make us conclude that the integral $S(\mathrm A) = \left(\displaystyle\int_{\mathrm O}^{\mathrm A} \frac{đQ}{T}\right)$ takes the same value for two equilibrium states and doesn't depend on which reversible path connect the states ($\rm O$ is the standard state). And this is entropy.
Now, in order to show the association of the Second law with entropy, we would utilise $\rm(II.a)\;.$
Consider now $\mathtt{ I''}$ as a non-reversible transformation replacing the reversible $\mathtt I$ while the others remaining the same as above.
Now, applying $\rm(II.a),$ we have,
\begin{align} \oint_{\mathrm A \mathtt{ I''} \mathrm B \mathtt{I'}\mathrm A } \frac{đQ}{T} & \leq 0 \\ \implies \left (\int_{\mathrm A}^{\mathrm B} \frac{đQ}{T}\right)_{\mathtt{I''}} + \left (\int_{\mathrm B}^{\mathrm A} \frac{đQ}{T}\right)_{\mathtt {I'}} & \leq 0\\ \implies\left (\int_{\mathrm A}^{\mathrm B} \frac{đQ}{T}\right)_{\mathtt{I''}} -[S(\mathrm B) -S(\mathrm A)] &\leq 0, \end{align}
Therefore, $$S(\mathrm B) -S(\mathrm A)\geq \int_{\mathrm A}^{\mathrm B} \frac{đQ}{T}\;.\tag{IV}$$
For an isolated system, $đQ = 0,$ hence, $$S(\mathrm B) -S(\mathrm A)\geq 0\tag{IV.a}$$
So, the Second law predicts that for an isolated system, for any transformation, the entropy of the final state must not be less than the initial state.
For a general system (not isolated), the Second Law states:
$$\Delta S_\textrm{universe} = \Delta S_\textrm{system} + \Delta S_\textrm{source/reservoir/surroundings} \geq 0\;.\tag V$$
Why is this statement true and exactly what does it have to do with entropy?
Because perpetual machine doesn't exist.
While the first law forbids the construction of perpetual machine from which emanates energy, it provides no limitation on the transfer of energy into one form or other.
There could be possibility of thermal energy being totally converted to work or vice-versa.
It is worthy to quote Fermi:
There are very definite limitations, however, to the possibility of transforming heat into work. If this were not the case, it would be possible to construct a machine which could, by cooling the surrounding bodies, transform heat, taken from its environment, into work.
Since, the supply of thermal energy contained in the soil, the water, and the atmosphere is practically unlimited, such a machine would, to all practical purposes, be equivalent to a perpetuum mobile, ....
The Second Law forbids that.
As for why it is related to entropy, let me re-iterate the fact that the very definition of entropy change comes from Clausius Inequality, which is explicitly shown above, that in-turn is a re-statement of the Second Law since, its deduction is based on the validity of Kelvin's postulate and thus Clausius' postulate.
Also, the very interpretation of Second Law in the light of entropy viz., the entropy of the universe(system plus sources) never decreases would get contradicted had thermal energy been exchanged from hotter source to cooler source.
In terms of the change in entropy of the system, why is it true that no heat engine can operate at 100% efficiency?
An engine can't use all the thermal energy it received from the hot source for work during a cycle.
Note the word cycle.
If a system has to operate on a cycle, then the entropy increase of the system caused due to the receiving of thermal energy from the hot reservoir must have to be nullified out by an entropy decrease.
The engine does so by giving up thermal energy to the cold reservoir so that there is no change in entropy of the engine during the cycle.
That's the reason why it has to lose heat energy and thus averting the case of having $100~\%;$ and that is the last nail in the coffin of perpetual motion of second kind.
It is worthy to re-state the statement of Second Law in the present context of an engine working in a cycle:
It is impossible to construct an engine which will work in a complete cycle, and produce no effect except the raising of a weight and cooling of a heat reservoir.
Note, as asserted at the outset of this post, the Carnot efficiency is the maximum efficiency for a given set of temperatures; all other non-reversible engines have efficiency lesser than the former.
However, even the Carnot engine can't have $100~\%$ efficiency for it would contradict the Second Law and it's impossible for perpetual machine doesn't exist.
References:
$\bullet$ Thermodynamics by Enrico Fermi.
Best Answer
Although this statement of the second law is rather imprecise, the device you describe (which I will call a refrigeration engine) is indeed forbidden by it.
We already know of functioning devices which can take work and convert it to thermal energy, which we can generically call heaters. So, with your refrigeration engine, you could couple it with a heater in the hot reservoir to further increase the heat in the hot reservoir. Then you would wind up with a combined system that violates Clausius’ statement.
Now, since we know that heaters exist, and by Clausius’ statement the combined refrigeration engine/heater cannot exist, we can conclude that the refrigeration engine cannot exist.