Let $M$ be a special structure. I'm trying to proof that every relation in $M$ which is first-order definable with parameters has cardinality $< \omega$ or $= \lambda$.
By a first-order definable with parameters relation I mean a set $A = \left \{ \psi(a_1, \cdots, a_m, b_1, \cdots, b_n): a_1, \cdots, a_m \in M,\, b_1, \cdots, b_n \in X, \, \psi(\overline a, \overline y) \text{ formula} \right \}$ for fixed $m$ and $X \subset M$.
I don't know even how to start this question. If I suppose that a set $A$ as above has cardinality $\geq \omega$, we proof that $|A| = |M|$, but how can I proceed?
In this answer I will not distinguish between elements/variables and finite tuples of elements/variables (so you may read every lowercase letter as if it denotes a finite tuple).
First I should say that your definition of "definable" it's not quite right. The way you defined it, every set would be definable. The correct definition is that $A$ is definable (in $M$) if there is a formula $\phi(x,y)$ and $b \in M$ such that $$ A = \{a \in M : M \models \phi(a,b)\}. $$ We call $b$ the parameters.
Let me also recall the definition of a special structure here (to introduce some notation at the same time). A structure $M$ of infinite cardinality $\kappa$ is special if it is the union $\bigcup_{i < \kappa} M_i$ of a chain $(M_i)_{i < \kappa}$ such that for every $i < \kappa$ the structure $M_i$ is $|i|^+$-saturated.
Now that is out of the way, we can actually have a look at your question. Let $A \subseteq M$ be infinite and $|A| < |M|$. Suppose that $A$ is definable by some $\phi(x, y)$ with parameters $b$. We will aim for a contradiction. Since $b$ is just a finite tuple of parameters, there will be some $\lambda < \kappa$ such that $b \in M_\lambda$. We may assume that $|A| \leq \lambda$ (otherwise replace $\lambda$ by $|A|$). Now define $$ \Sigma(x) = \{x \neq a : a \in A \cap M_\lambda\} \cup \{\phi(x, b)\}, $$ then clearly $\Sigma(x)$ is finitely satisfiable. So we can extend $\Sigma(x)$ to a complete type $p(x)$ over $(A \cap M_\lambda) \cup \{b\}$. Since $|(A \cap M_\lambda) \cup \{b\}| < \lambda^+$ and $M_\lambda$ is $\lambda^+$-saturated we then must be able to find a realisation $c \in M_\lambda$ of $p(x)$ and thus of $\Sigma(x)$. But that means $M_\lambda \models \phi(c, b)$, so $c \in A \cap M_\lambda$ while the first part of $\Sigma(x)$ says that $c$ must be different from every element in $A \cap M_\lambda$. We thus reach our desired contradiction, and we can conclude that of $A$ is infinite and $|A| < |M|$, then $A$ cannot be definable in $M$.