I have a Fanuc 18i controller on a sliding head lathe - it also has limited memory, so I regularly delete programs.
On mine the procedure is simple enough: Select "edit" mode, type the number of the program to delete, for example O0021, press the delete key, a message appears asking if I want to delete the program, then press softkey "execute".