TL;DR (short response)
$$ ``\text{operation"} \neq ``\text{function"}. $$
But if we remove references to functions from the question, the question is a good one.
Discussion
The problem with the question as posed is that it does not give clear and consistent definitions of the types of objects that are named $f$, $x$, and $y$ in the initial statement.
Suppose we just want to solve equations that deal only with real numbers, so no complex numbers or other mathematical values. Then if $x$ and $y$ are numbers (no matter how they are written in the equation) and $f$ is restricted to functions with domain and codomain $\mathbb R$,
$$ \forall f : x = y \implies f(x) = f(y) $$
is true. It's also irrelevant to many of the techniques for solving equations.
As an example, let's solve
$$ t^2 - 3t + 2 = 0. \tag A$$
A possible first step is to factorize the left-hand side. We get
$$ (t - 2)(t - 1) = 0. \tag B$$
Where is the function that we performed on both sides? It doesn't exist;
there is no function $f: \mathbb R \to \mathbb R$ that tells us how to factorize a quadratic polynomial.
So if that's how we interpret $f$, $x$, and $y$, the question is not about how to solve equations in general, but only about a very limited methodology that involves simple operations such as adding $3$ to both sides or dividing both sides by $2$. Anything that requires you to actually look at what's inside an expression to decide what to do with it is off the table.
But let's suppose that $x$ doesn't just represent the value of the left-hand side of the original equation; let's suppose $x$ actually represents the contents of the expression. We might express $x$ as a syntax tree of some sort. To distinguish the value on the left-hand side of Equation (A) from the particular way the left-hand side is written syntactically, I'll write
$\langle\!\langle t^2 - 3t + 2\rangle\!\rangle$ when I mean the expression itself as a syntactical object and $t^2 - 3t + 2$ when I mean the value of the expression.
If $x$ and $y$ are syntactical objects and $f$ performs transformations of syntactical objects, then a method of factorizing simple quadratics might be an example of $f$. But now the statement
$ \forall f : x = y \implies f(x) = f(y) $
is irrelevant to all but a very uninteresting set of problems,
because
$\langle\!\langle t^2 - 3t + 2\rangle\!\rangle \neq \langle\!\langle 0\rangle\!\rangle$.
(Just look at the two expressions: they don't even have the same number of terms.)
In short, I just don't see any obvious way to correctly interpret the notation in the question so that it applies generally to the things people actually do when solving equations.
But it might make sense to say -- without attempting to use anything that looked like functional notation -- that when we apply a technique in one step of solving an equation, starting with an equation written one way and ending with an equation written another way, we have an expectation that if the technique has any validity, all solutions of the first equation ought to be solutions of the second equation.
I think the answer to the question phrased this way is that people lose solutions because they use techniques that are only "almost" valid, that is, they do something that largely resembles a valid technique but they omit some detail that was needed in order to make the technique valid in all cases.
Overlooking a possible division by zero is one of these mistakes.
Another mistake is assuming $g(f(x)) = x$ when $g$ is the so-called "inverse function" of $f$ but is not a true inverse of $f$ (for example, if $g$ is the square root or the arc sine).
Original long response
Your premise is wrong.
Not everything we do while solving an equation is a function.
Many of the operations we might perform on the two sides of an equation are not functions at all.
For example, suppose we have the following equation at some point in a derivation, where the value of $n$ is unknown (but it is known that
$n\neq 0$):
$$
n^2 - n = n \sin(\theta). \tag1
$$
And suppose the next step is, "divide by $n$."
(Or, "cancel a factor of $n$ on both sides.")
Then the next equation we write is
$$
n - 1 = \sin(\theta). \tag2
$$
Just to be crystal clear, we have just performed an operation
that is expressed by the following implication:
$$
n^2 - n = n \sin(\theta) \implies
n - 1 = \sin(\theta). \tag3
$$
This is a perfectly legitimate operation and people do operations like this all the time while solving equations.
You claim that every operation performed in the solution of an equation can be described in the following form, where $f$ is a function:
$$
x=y \implies f(x)=f(y). \tag4
$$
If this claim were true, there would be a function $f$ for which you could
plug $x = n^2 - n$ and $y = n \sin(\theta)$ into formula $(4)$
and the result would be formula $(3)$, that is,
$f(x) = n - 1$ and $f(y) = \sin(\theta)$.
Remember, formula $(4)$ is your framework.
If you claim it applies to all operations people perform while solving equations, it is your responsibility to show exactly how you can use a function $f$ to derive Equation $(2)$ from Equation $(1)$ in a logically valid manner when $n \neq 0$.
You have to start with the expression $n^2 - n$ on the left hand side of one equation, and then somehow by applying your function $f$ to $n^2 - n$ you have to arrive at the value $n - 1$ which you write on the left hand side of the next equation.
So right away, if you can't define a function $f$ such that
$f(n^2 - n) = n - 1$, you have failed to model formula $(3)$ using formula $(4)$, and your claim about how we solve equations is immediately proved false.
Now, if all you know about $n$ is that $n \neq 0$,
what do you mean when you say $f(n^2 - n) = n - 1$?
If you don't mean that $f(n^2 - n) = n - 1$ for all $n \neq 0$,
what do you mean?
Whatever it is, it's not what people usually mean when they say they can derive Equation $(2)$ from Equation $(1)$ when $n \neq 0$.
So $f(n^2 - n) = n - 1$ must be true for $n = -1$ and also true for $n = 2$.
Case $n = -1$: then $$x = n^2 - n = (-1)^2 - (-1) = 2$$ and
$$f(2) = f(x) = n - 1 = (-1) - 1 = -2.$$
Case $n = 2$: then $$x = n^2 - n = 2^2 - 2 = 2$$ and
$$f(x) = n - 1 = 2 - 1 = 1.$$
Summary: From the first case, we conclude that $f(2) = -2$.
From the second case, we conclude that $f(2) = 1$.
But you can't have $f(2) = -2$ and also $f(2) = 1$ for any function $f$.
The problem here is that the result of performing an operation on both sides of the equation does not always depend only on the value of the entire expression on each side of the equation, as you implicitly assume when you write $x = y \implies f(x) = f(y)$.
The result of the operation can also depend on elements inside the expression on each side of the equation, which you cannot express in a function
$x \mapsto f(x)$.
That's what I meant when I said that many operations are not functions.
Many of the operations that you can apply on both sides of an equation
(such as add $3$ or divide by $2$)
really are functions.
But in the solutions of equations,
people often perform operations (I would rather say manipulations) that are not functions.
These manipulations use details buried inside the expressions on each side, not just the value of the expression on each side, to decide what to write in the next equation.
But I don't have any examples in mind where any operation loses a solution, other than cases of division by zero. (Some divisions by zero are well-concealed, but nevertheless they are division by zero.)