Solution was to create a folder called tmp like this: /usr/share/phpmyadmin/tmp.
Also make sure that the user (or group) running the webserver (e.g. Apache) has write access to the newly created tmp folder. Consequently, change the ownership to that user or add write access for all users. The latter one might not be really advisable.