@Gerardo's answer is only correct at the equator. The gdaldem doc notes those scale values are for "LatLong projections near the equator"
To calculate the scale or Z factor (inverse of scale) at other latitudes for a dem with vertical units in metres, you can use the following equations:
s=111320*cos(latitude*pi/180)
z=1/(111320*cos(latitude*pi/180))
where: 111320 is the length of one degree at the equator in metres (based on WGS84, you can use 111111 if that's easier to remember, or you have an appreciation of history) and latitude is the latitude at the centre of your DEM.
You can quickly calculate the scale/z factor in Excel/Libre Office Calc with the following formulas:
For -s scale parameter
=111320*COS(latitude*PI()/180)
or
=111320*COS(RADIANS(latitude))
For -z z factor parameter
=1/(111320*COS(latitude*PI()/180)
or
=1/(111320*COS(RADIANS(latitude))
You can even use a simple Google search:
111320 * cos(latitude deg)
or
1/(111320 * cos(latitude deg))
E.g. scale and z factor for Latitude = 38.5S
For DEMs with vertical units in feet, just convert the length of one degree at the equator in metres to feet, i.e 3.28 * 111320 = 365130. So your equations become:
s=365130*cos(latitude*pi/180)
z=1/(365130*cos(latitude*pi/180))
Alternatively, you can reproject your DEM to a projected coordinated system (also suggested by the gdaldem docs).