PMI must be removed when LTV is scheduled to hit 78% based on the original value of the home and the original amortization schedule (Automatic Termination). At 80% LTV based on current value you may get it removed but at that point there are additional caveats like a good payment history, no additional liens, etc. (Borrower-Requested Cancellations).
From the Federal Reserve's Compliance Handbook for Homeowners Protection Act:
There is no provision in the automatic-termination section of the act,
as there is in the borrower requested PMI cancellation section, that
protects the lender against declines in property value or subordinate
liens. The automatic-termination provisions make no reference to good
payment history (as prescribed in the borrower-requested provisions)
but state only that the borrower must be current on mortgage payments.
So, since you have paid extra to get below 78% ahead of schedule, the Automatic Termination rules don't apply and you are subject to the Borrow-Requested rules which can include an appraisal.
If you were at 78% based on original value and amortization schedule they are obligated to remove PMI. They should have a instructions for requesting removal of PMI, and there would be no reason for that to include an appraisal. If they declined to remove PMI without an appraisal in this context, you'd need to file a complaint with the CFPB or pursue legal action.
You'll want to review the schedule to see how far ahead you are to decide if the appraisal is worth it.
FHA loans have different rules for their Mortgage Insurance Premium, I assumed a traditional loan since you mentioned PMI.
Edit: I had completely missed that the 78% Automatic Termination is based on schedule not actual LTV, thanks to @Guest5