Can you sacrifice a creature to Altar of Dementia in response to a removal spell targeting it?

Yes, this works. Altar of Dementia is an activated ability (cost: sacrifice a creature; effect: target player mills that many cards). You can activate it any time you have priority, including in response to a spell or ability on the stack.

When a removal spell (say, Murder) is cast targeting your creature, it goes on the stack. Before it resolves, you receive priority and may activate Altar of Dementia, sacrificing the targeted creature as part of the cost. Paying an activation cost — including sacrificing — happens immediately when you activate the ability, before anything else can respond (CR 602.2).

Once the creature is sacrificed, it leaves the battlefield and no longer exists as a legal target. When Murder tries to resolve, it checks for its target and finds it invalid. Per CR 608.2b, a spell or ability with all illegal targets is countered on resolution, so Murder simply does nothing.

Concrete example: Your opponent casts Murder targeting your 5/5 creature. In response, you tap Altar of Dementia and sacrifice the 5/5 as the cost, causing your opponent to mill 5 cards. When Murder resolves, the creature is gone — it has no legal target and is countered.

Note that this only works if the removal spell targets the creature. Removal that doesn't target (e.g., Wrath of God) cannot be dodged this way, though sacrificing in response still removes the creature from the battlefield before the wrath resolves.