This can occur when the locale is incorrect, or when glibc is built with "C" locale, which does not support unicode characters. Powerline uses non-breaking spaces (2-byte) and also uses 2-byte unicode characters for the triangles. For each one of these characters, the shell (not powerline) thinks that 1 extra character has been printed. If you have 5 spaces and 3 triangles in the prompt, then the prompt will wrap 8 characters before it hits the end of the line. From there everything behaves incorrectly. This only relates to Powerline in the sense that Powerline uses unicode characters in the prompt.
The fix is to correct the locale so the shell understands 2-byte unicode. You can run "locale" to see if the shell is using "C", in which case it needs to be fixed. For my application, we were running Powerline in a Docker image running Centos Linux. We had to fix the locale in /etc/yum.conf to use the lowercase form of utf8 like so:
sed -i 's/UTF-8/utf8/' /etc/yum.conf
Then rebuild glibc-common with the fix:
yum reinstall glibc-common
After that, new terminals behaved and the prompt wrapped correctly. We then modified our Docker image to fix yum.conf before installing glibc. However, we found one of our modules was changing the locale back to C (LANG="C"), so we used the LC_ALL env var to override it:
LC_ALL=en_US.UTF_8
After that, all new terminals behaved correctly.