My assumption in this posting will be that the issue cannot be worked out with the manager in question.
Sometimes individuals with a "strong personality" such as this are brought on with the specific purpose to be a 'hit man' who can clean house.
With a manager such as this it becomes simply a matter of time and often happens through natural attrition, such as when the manager starts giving lower evaluations and treating people like you describe, so those who cannot handle it leave.
So this may be a strategic move from above.
In this case openly appealing to the higher-ups for transfer may backfire since you are offloading decision-making onto them, whereas the whole point was for them to clean house without getting directly involved.
With this in mind I would second @Blam's suggestion to "Apply outright for another position when one becomes available." You may want to keep this as quiet as possible and apply to another organization with the company with little or no overlap of work with your current team. (This may or may not be feasible in your case, but would be the best option as it would reduce the chances of interfacing with this manager in the future.)
Find a mentor within your organization (again, preferably in another department/building). If you are in a union, you would benefit from finding an ally who is a Union Representative with long tenure in the company, who knows the ins and outs of the union contract.
Have a conversation with that person without naming names, talking from principles and objective facts rather than feelings. See what they have to say about how to navigate the internal job market to secure a position with a different unit/team. (Again, this person does not need to be in that organization where you want to move; they can be in a completely unrelated role, as long as they have experience in the organization and can relate to your predicament).
Do your homework. Research internal postings, job responsibilities, qualifications, and figure out where you might fit in outside of your immediate department. Think about the skills or education that you have but are not currently using, and see if you can 'dust off' these parts of your resume (which may require substantial revision when applying for different kinds of positions). If you are geographically mobile, consider expanding your search to your company's offices in other cities (have a 2nd and 3rd best position options).
Chances are if you go through an interview process for another position, your manager might find out about this just as the hiring manager on the other team is getting ready to make you an offer (it may be company policy to consult with current manager).
Be ready for this and make sure to approach this issue in calm, matter-of-fact and relaxed way if your manager decides to confront you about this. Do not make this personal about you and him. Rather, cite your own professional development goals and reasons such as interest in gaining experience in other facets of the company's work to round out your skill set.
Be composed, strategic, focused and proactive. Do not make hasty moves, but methodically do your research/gather information about alternative opportunities and ways to navigate this issue (as you are already doing by posting a question on this forum). Keep calm and carry on ;) Good luck!