es fácil... como me lo explicaron a mi es pensar un SELECT con los casos que queres borrar y en vez de SELECT * FROM ponés DELETE FROM
O sea, quiero borrar a todos los que tengan apellido q empiece en A de la tabla nombre
DELETE FROM nombre WHERE apellido = 'A%'
Si te tira algún error puede ser que no tengas acceso al comando DELETE.
En caso de ejecutar la consulta en PHP deberías poner un or die(mysql_error()) para ver el error
Código PHP:
mysql_query("DELETE FROM nombre WHERE apellido = 'A%'") or die(mysql_error())