# Python 2:
os.walk(u'.')

# Python 3:
os.walk('.')

>>> u'я'.encode('cp866')
b'xef'
>>> u'я'.encode('cp1251')
b'xff'
>>> u'я'.encode('utf-8')
b'xd1x8f'

>>> b'xef'.decode('cp866')
u'я'
>>> b'xef'.decode('latin-1')
u'ï'

#!/usr/bin/env python2
import io
import sys

with io.open('files_to_remove.txt', encoding='utf-8') as file:
    for path in file:
        path = path.strip()
        try:
            os.remove(path)
        except OSError, e:
            print >>sys.stderr, "warning: can't remove %r, reason: %s" % (path, e)