If it is saying that deleting the images will delete them from iCloud I think that means they are actually in iCloud rather than on your Mac.
Have you signed up for iCloud Photo Library and uploaded the images to iCloud? How much iCloud storage are you paying for? This would offer the biggest clue to whether this is the case.
An alternative would be to move your photo library to a separate storage device, our colleagues at Macworld US have recently published this article about doing that: click here