While a manual transmission in the Subarus seem to run high at highway speeds (according to this website, 3200 @ 70mph is normal ... this to me who runs a vehicle which maintains ~1800-2000rpm at 70mph seems high, but nothing like what you are experiencing), running over 3500rpm at 50mph seems quite a bit excessive. This could be the cause of your heating issues. I don't think it has anything to do with the A/C, as it is probably just making the problem more noticable, but not causing it.
You could be experiencing one of two issues as I see it:
If you have a manual transmission, your clutch may be majorly slipping ... I don't think this is the issue. If the clutch is working correctly, for any selected gear at a specific engine speed, you can expect a specific vehicle speed. It's mechanical; it's mathmatical. It will be the same between different vehicles of the same model and year. The only way it is going to be different is if your clutch is slipping. In your case the clutch would have to be slipping like a mad beast. This would probably be very obvious to you and soon enough the clutch would not be working at all.
If you have an automatic transmission, it may not be going into overdrive. This I believe is probably your issue. If the transmission is not going into overdrive as it is supposed to, it will be running at the higher RPM and will be working much harder than normal. When an engine is forced to work hard for a long period of time, it heats up and will generally start to get heat soaked. Once it gets heat soaked, it will not be able to shed heat as easily and thus you'll be seeing a rise in engine temperatures. I notice you also say it is heating up, but not that it is exactly "overheating".