glycogen is stored in your liver and muscles (men have a bigger reserve then women). there is an order to energy metabolism, glycogen (or glucose) > carbs > fat > protein. you actually use up your glycogen storage fairly quick but as you eat throughout the day, it's storage gets replenished.
after a few days of not eating (and depletion of carbohydrate reserves) your body starts to break down fat in order to get the necessary building blocks for ATP (acetyl groups which gets converted into Acetyl CoA) the problem with this is the release of ketone acids (aka ketoacidosis, which is a problem with low carb diets). your body actually starts to break down fats earlier do to the glucose sparring effect. the nervous system and brain prefers glu as their main source of energy and your body will shift it's energy consumption around to reserve all glucose for the brain.
after 3-4 days of starvation and the depletion of carbs/fat reserves, the body will get energy via non carb/fat sources via gluconeogensis. primary sourc is through protein degradation breakdown down the polypeptide bonds to amino acid components. the amino acids are broken down in the liver and kidneys into pyruvate and enter the citric acid cycle.
carbs of made from polysaccharides, aka sugar building blocks
protein is made from polypeptides, aka amino acid building blocks
fat is made from triglyceride and free fatty acids
this is it in a nutshell, thanks for the good question, it's helping me reinforce and study for my dental admissions test next week
also, typical glycogen storage is 2k a day. the reduction of 500 calories from your diet is dependent on your Energy (in) vs. Energy (Out) so this varies from person to person.