(With apologies for reviving an old question which already has many answers) here are two perspectives:

1. Ponder the fact that 

 > $\mathsf{Set}$ is complete and cocomplete. $\mathsf{Rel}$ is not.

 For example, the total relation $1 \to 2$ and the graph of your favorite function $1 \to 2$ fail to have a coequalizer in $\mathsf{Rel}$; see [here](https://math.stackexchange.com/a/870483/45082) for a proof. See also the Milius paper linked to by Martin Brandenburg above for an example of an $\omega$-chain which doesn't have a colimit in $\mathsf{Rel}$.

 Thus we "reduce" the question of why $\mathsf{Set}$ is "more fundamental" than $\mathsf{Rel}$ to the question of why limits and colimits are so fundamental to category theory. Loosely, I'd say that limits and colimits are to category theory as universal and existential quantifiers are to logic -- without them, you're simply very limited in the kinds of things it's possible to say at all.

2. An object $X$ of a category $\mathcal C$ is studied by looking at the set of possible "measurements" $\mathcal C(X,A)$ by objects $A$, or dually by "probing" via the set of maps in $\mathcal C(B,X)$. In category theory, we get a lot of juice out of the fact that these two ways of looking at an object $X$ are quite different, and we can play them off one another. But in a self-dual category like $\mathsf{Rel}$, you can't tell the difference between the object doing the measuring and the object being measured -- it's like there's feedback in the measurement process. Everything is simply too jumbled together to make sense of the data you're recording. To mix metaphors some more, $\mathsf{Set}$ is like a cleaner operating room to work in than $\mathsf{Rel}$, or an experimental environment where more of the environmental variables are well-controlled.