404 page wp_title()

I don’t reproduce such bug. To set the 404 page language, there are several cases:

1. You set the language from the content:
The language of the 404 page is set from the last browsed page or, if this is the first visit, from the browser preferences with a last fallback to the default language

2. You add the language code to all urls:
a. If the language code is included in the wrong url, then the language is set from this code
b. if there is no recognized language code in the url, then the language is set as in 1.

If you are on the 404 page, switching to a different language should send you to the home page in that language

I’m sorry the problem doesn’t affect only 404 page.
Here’s how it is – I use 2 languages for my page
English and Lithuanian, I need admin page to be in my language(Lithuanian), I set
define('WPLANG', 'lt_LT');
so far so good, but I need my archive, 404, and some others pages to be in 2 languages:
domain/en/non-existing-page – should generate 404 page in English,
domain/lt/non-existing-page – should generate 404 page in Lithuanian.
wp_title() function generates _e(‘Page not found’); and thus it’s translated in account of define('WPLANG', 'lt_LT');, it ignores /en/,/lt/ language codes and translates string according to defined language. And it happens anywhere a string is translated without theme text-domain. I can work around this problem, by adding needed strings to themes localization, and then translating string using themes text domain, e.g. _e('Page not found', 'theme-text-domain');

So in short
_e('Page not found', 'theme-text-domain'); will translate string depending from language code /en/,/lt/
_e(‘Page not found’); will translate string depending from defined language define('WPLANG', 'lang_LANG');

Now the question is, if it’s really a bug, or it is just the way it works?

There is a problem with your setup as Polylang should do what you expect.

Could you test with a default theme such as twenty twelve and no other plugins activated to check that there is not a conflict somewhere?

Could you precise your Polylang settings?

I have done as you told, and found out that the problem was caused by
WP Events Calendar plugin which is no longer supported, I guess it’s time to search for an alternative.
Anyways thanks for clearing things up!