That one was removed in 2d3c709. Do you have any custom plugins installed?

Nop but I did the following upgrade path :
2.10 -> 2.11.2

I actually have https://github.com/gboddin/MysqlPostConnectCommands but it shouldn't matter

Just updated to 2.12.1, still the same issue

FYI the piwik distribution for our cluster is built with :

#!/bin/bash
echo Reseting
[ -d piwik ]&&rm piwik -Rf
echo Extracting piwik ... 
wget -O - "https://builds.piwik.org/piwik-latest.tar.gz"|tar -xz
[ -f "How to install Piwik.html" ]&&rm "How to install Piwik.html"
cd piwik
curl -sS https://getcomposer.org/installer | php
php composer.phar install -o --no-dev
rm composer.*
rm *json
git clone https://github.com/gboddin/MysqlPostConnectCommands.git plugins/MysqlPostConnectCommands
find -type d -name .git|xargs rm -Rf
find -type f -name .git|xargs rm -f
find -type f -name .gitignore|xargs rm -f
find -type f -name .gitattributes|xargs rm -f
find -type f -name .gitmodules|xargs rm -f
find -type f -name .gitkeep|xargs rm -f
cd ..
tar cz piwik > piwik-distrib.tar.gz

Hi!
I also have "Visitors" - "Provider_SubmenuLocationsProvider" link leading to "Visitor Map" page, and looks like the problem is in updating process.
When updating Piwik (2.8.3 -> 2.13.1), I unzipped the latest version and overwrote existing files, so I've got all added and changed files.
But removed files (like plugins/Provider/Menu.php) was left in their places and now they are somehow autoloaded.
However, if I simply remove it, I get No entry or class found for 'Piwik\Plugins\Provider\Menu' error.

UPD: Clearing piwik/tmp folder fixed it.

FYI: we will try to fix this bug "correctly" in this issue: #7986