To be honest, those two parameters may seem to be slightly similar but provide a totally different functionality.
From their documentation on search:
Only fetch entries that match a given search query. (See Searching for the syntax and > available search attributes.)
Which means whatever you pass in
.search(query), and there is a rather complex list here, will actually 'search' Craft for the query string you specify.
On a different note,
Only fetch entries that are related to certain other elements. (See
Relations for the syntax options.)
This on the other hand only 'relates' to other entries, meaning its not performing a fill search on Craft, only the entries. A detailed reference on relations can be found here.
As far as performance, the two are unrelated as it really depends on what you are trying to accomplish.
Hope this clears it up for you!