Why is a category/ tag name prefixed to title of every page?

I’ve found the cause.

All in one SEO Pack plugin 1.6.14.5 is guilty (perhaps it’s not guilty by itself but also due to the multisite setup of my site and other plugins I’ve just installed conflicting it). Disabling the plugin resolve the problem immediately. I’m upgrading it and will use an alternative if it doesn’t work out. Thanks @LeaCohen for pointing me to the right redirection.

Updates
Instead of deactivating the plugin, disabling the auto-rewrite title in settings of the plugin is sufficient.
At the same time, just FYI, All-in-one SEO Pack plugin version 1.6.13.8 works just fine for WordPress multisite 3.4.2. I can no claims about the possible conflicts between this and any other WordPress plugins