There are two ways of doing this:
- As others suggested in the comments --- which given the amount of structure this problem admits is probably the fastest --- one expresses each element of the new basis in terms of the old basis and evaluates $f$ on it using linearity.
For example $e_1=\frac12(e_1+e_3)+\frac12(e_1-e_3)$ (and this decomposition is unique because $\{e_2,e_4,e_1+e_3,e_1-e_3\}$ is a basis of $\mathbb C^4$), so because $f$ is linear we compute
\begin{align*}
f(e_1)&=f\big(\tfrac12(e_1+e_3)+\tfrac12(e_1-e_3)\big)\\
&=\tfrac12f(e_1+e_3)+\tfrac12f(e_1-e_3)\\
&=\tfrac12 i(e_1+e_3)+\tfrac12 (-i(e_1-e_3))\\
&= (\tfrac12i-\tfrac12i)e_1+(\tfrac12i-(-\tfrac12i))e_3=0\cdot e_1+i\cdot e_3=ie_3\,.
\end{align*}
Doing the same with the other elements of the new basis yields $f(e_2)=-e_2$, $f(e_4)=-e_4$, and $f(e_3)=$
\begin{align*}=f\big(\tfrac12(e_1+e_3)-\tfrac12(e_1-e_3)\big)&=\tfrac12f(e_1+e_3)-\tfrac12f(e_1-e_3)\\&=\tfrac12 i(e_1+e_3)-\tfrac12 (-i(e_1-e_3))\\&= (\tfrac12i+\tfrac12i)e_1+(\tfrac12i-\tfrac12i)e_3=ie_1\,.\end{align*}
Finally the corresponding matrix has to achieve precisely this transformation, that is, $e_1\mapsto f(e_1)=ie_3$, $e_2\mapsto f(e_2)=-e_2$, and so on. This is what gives you the columns of this matrix, resulting in
$$ \begin{pmatrix} 0&0&i&0\\ 0&-1&0&0\\ i&0&0&0\\ 0&0&0&-1\end{pmatrix}\,.$$
- Another way is to work exclusively with matrices: The idea is to find a matrix which describes how one basis transforms into the other basis and then use it to "modify" the original representation matrix
$$
M=\begin{pmatrix}
-1&0&0&0\\
0&-1&0&0\\
0&0&i&0\\
0&0&0&-i
\end{pmatrix}
$$
to described how $f$ acts on the new basis. [Check for yourself that (a) this matrix indeed describes how $f$ transforms "the" old basis $\{e_2,e_4,e_1+e_3,e_1-e_3\}$, and (b) that --- although we arranged the old basis elements in a certain order here --- this does not matter for the new representation matrix because the order will be "corrected" by the basis transformation matrix].
Now to get more precise, if the matrix $P$ "maps the new basis to the old one" then the representation matrix we are looking for is given by $P^{-1}MP$.
The reason this works can be sketched as follows:
$$
\substack{\text{vector in}\\\text{new coordinates}}\quad\overset{P}\longrightarrow\quad\substack{\text{vector in}\\\text{old coordinates}}\quad\overset{M}\longrightarrow \quad\substack{\text{image under }f\text{ in}\\\text{old coordinates}}\quad\overset{P^{-1}}\longrightarrow\quad\substack{\text{image under }f\text{ in}\\\text{new coordinates}}
$$
As for the actual computation: Recall that the initial basis of $V$ is $\{e_2,e_4,e_1+e_3,e_1-e_3\}$ and the target basis is $\{e_1,e_2,e_3,e_4\}$. Then, because
\begin{align*}
\text{new basis vector}_1=e_1&=\frac12(e_1+e_3)+\frac12(e_1-e_3)\\
&=\frac12\text{old basis vector}_3+\frac12\text{old basis vector}_4\end{align*}
the first column of $P$ ($=Pe_{\bf 1}$) is:
$$
\begin{matrix}0\\0\\\frac12\\\frac12\end{matrix}
$$
Next $e_2=\text{old basis vector}_1$ so the second column of $P$ equals $(1,0,0,0)^\top$. Continuing this argument we eventually arrive at $P=$
$$\begin{pmatrix}0&1&0&0\\0&0&0&1\\\frac12&0&\frac12&0\\\frac12&0&-\frac12&0\end{pmatrix}$$
The last thing we need is the inverse of $P$. We can either compute $P^{-1}$ by inverting $P$ or --- because $P^{-1} $ describes how the old basis translates into the new one --- we can repeat the above process, but now the two bases are switched.
For the latter, e.g., $\text{old basis vector}_4=e_1-e_3=\text{new basis vector}_1-\text{new basis vector}_3$ so the fourth column of $P^{-1}$ is given by $(1,0,-1,0)^\top$. Either way one finds $P^{-1}=$
$$ \begin{pmatrix}0 &0&1&1 \\1 &0&0&0 \\0 &0&1&-1 \\0&1&0& 0 \end{pmatrix}$$
With this all that is left is to multiply these matrices in the correct order: computing $P^{-1}MP$ indeed yields the same matrix we found via the previous method.
As a final remark let me emphasize that in this example the first method is easier because $f$ in the old basis was already of a rather convenient form. For generic linear transformations the second method is better suited because expanding the image of $f$ in different bases can become quite cumbersome, and this method outsources this expansion step to a simple matrix multiplication.