How to use iCloud for photo backup
Photo Stream only saves the last 1000 photos and doesn't include videos. An iPad backup to iCloud doesn't include photos or videos. That tells me it is not safe for you to delete anything at the moment.

I think your best bet is to install one of the other cloud services that support syncing photos. Both Dropbox and SugarSync can do backups although Dropbox renames all your photos so SugarSync might be a better choice. There are other services as well but these are the two I happen to use the most.