I am trying to create a slope map in ArcMap out of a DEM.
I used the Slope Tool (Spatial Analyst), selected my DEM as input and degrees as an output result.
There I got the message that "The Z units of the output geographical spatial reference are undefined. A default Z factor of 1 was used". I pressed ok and I got this result:

As I can understand (this is the first time I use the slope tool, I'm new to ArcGis Suite) almost all my values are within the range of 89.6 - 89.9 degrees something that is clearly wrong, as my study area is this one:

I tried to create more classes in Symbology tab but I couldn't select more than three in Natural Breaks (Jenks) classification.
I am able to create 32 classes at Equal Interval option but this also doesn't change anything.
I tried my luck with Unique Values and I was asked to create them and I pressed ok but all the values are around 89.9.

I got the DEMs from Nasa Reverb, I connected two of them with Mosaic to Raster, created a shapefile (I selected the same projection, WGS 84 for the shapefile) and clipped my study area. Then I played with classes and colors in order to be as naturally looking as possible. I created a break at 0 Value in order to color the sea blue. Right after that I used the slope tool.
Any ideas for the slope degree values to be calculated correctly?

The inclination of slope will be calculated in degrees. – Georgios Alevizos Mar 11 '16 at 14:34
http://s27.postimg.org/btbrjpljn/Untitled.png
http://s30.postimg.org/8wk6zghk1/Untitled2.png
– Georgios Alevizos Mar 11 '16 at 15:04