Use aspas simples para a expressão que você usou:
sed 's/\//\\//g'
Nas aspas duplas, \
tem um significado especial, por isso você precisa invertê-lo:
sed "s/\//\\\//g"
Mas é mais limpo mudar o delimitador:
sed 's=/=\/=g'
sed "s=/=\\/=g"