原因はmkdirの中でOSのデフォルトエンコーディングに従ってmkdirに渡したpath文字列をエンコードしているため。 CPython実装を見ると、Py_FileSystemDefaultEncodingに従ってエンコードしているように見える。
cpython: 54c93e0fe79b Modules/posixmodule.c
Py_FileSystemDefaultEncodingは以下によるとLC_CTYPE依存。ここが正しく設定されてないのでPy_FileSystemDefaultEncodingがasciiになっており、os.mkdirの中でencodeに失敗していると思われる。
LC_CTYPEをen_US.UTF-8に設定するとPy_FileSystemDefaultEncodingがutf8になり、直った。