Замените все символы новой строки на "\ n" и замените все "\" на "\\", так же, как вы делаете со строковыми литералами:
def encode(s):
return s.replace("\\", "\\\\").replace("\n", "\\n")
def decode(s):
return s.replace("\\\\", "\\").replace("\\n", "\n")