Hola
no se como almacenas tus datos en la BD, ni como montas la ruta a la carpeta donde estan los archivos, pero en el codigo donde borras los registros has de poner algo asi:
Código PHP:
$dir = "/carpeta/carpeta"
$archivo ="nombre_archivo";
unlink($dir.$archivo); // aqui borras el archivo
Un saludo