Android - Cannot open Gallery to delete files, due to running out of space

While several hints can be found in the insufficient-memory tag-wiki, you case seems a little special ­– as you report to still have ~75 MB free (3 times the limit this error should be triggered).

This should even enable you to install a file manager (if you have not already done so, or a useful file manager was pre-installed). So in order to remove some photos/videos, you could start the file manager and look into the "usual locations". I've put that terminus in quotes, as different apps seem to place them into different locations.

Most photo apps save their images below /sdcard/DCIM, many use their own folders here. But as that is not related to your "phone storage" (SDCard, whether internal or external, should never trigger that issue), there might be a similar folder on phone storage. Irritates me a little, but I've read that before a few times. So make sure to use a file manager supporting this (alternatives below). Next to the DCIM folder, also check Pictures, Photos, Video, media, Music, and Documents, if they exist.

A good alternative to "local" file managers (apps that is), there's always the option of using ADB (if you've not yet installed it, check out Is there a minimal installation of ADB?). In case you're not used to the Unix/Linux command line, tools like QtADB might come in handy, offering a graphical file manager (amongst other things). On a rooted device, and with the help of adbd Insecure, you could even access the entire file system this way (careful!).