f.write("\n".join([str(i) for i in mlist]))

i.encode('utf8')
#или
str(i).encode('utf8')

def _decode_header(msg):
    header = {"from": None, "to": None, "subject": None}
    for h in header:
        txt, enc = decode_header(msg[h])[0]
        header[h] = txt.decode(enc) if enc else txt
    frm=header
    sbj=header
    return header,frm,sbj

...

#вот сама строка
mlist.append(';;'+_decode_header(msg)[1]['from']+'::'+_decode_header(msg)[2]['subject']+'::'+uidl+';;'+'\n')