お店側が客に「相席でもよろしいですか?」なら"Would you mind sharing a table?"。

でも、客自身が先に座っている人に「相席してもいいですか?」と直接尋ねるときは、「ここよろしいですか?」といったニュアンスになる"May I sit here?"なんてのがお勧め。同じ「相席する」でも状況によって違ってくるってわけです。