I had the same issue. In my case, it turned out I had a custom type with the same slug as the page I was trying to paginate. As a result, it was getting confused and routing my-page/page/2 to the type listing rather than back to the page.
Do you have a category or type with the same name as Page-name?
