Для Python <3 вы можете включить локаль: </p>
import locale
locale.setlocale(locale.LC_ALL, '')
А затем используйте параметр re.LOCALE
с вашими регулярными выражениями:
re.findall('\w+', 'Márquez', re.LOCALE)
Хотя, возможно, лучше использовать Unicode, хотя он требует декодирования данных и их кодирования в локальную кодировку.