Fel Hide was brought in for the Burning Crusade Expansion and so it can only be found in the Outlands. Fel Hide can only be obtained from skinning demons. Higher level demons will have a higher chance to drop Fel Hide. Best zones to farm Fel Hide is by skinning Wrath Hounds from Blade’s Edge Mountain, but a flying mount is required to get there.
See below for more information on where to farm Fel Hide.