The expression hovers halfway between being a figurative idiom and a literal phrase.
The literal aspect derives from the fact that US military, and this phrase is American, used to pay each rank according to specific pay grades. This payment system was later extended to many federal employees. An early example of that literal usage is found in the US Cases Court of Claims, 1883:
The law… indicates pay grades by description. Together they give to the retired chief engineer 75 per centum of the sea-pay of the pay grade which he held at the time of his retirement.
The first example that I can find of the figurative use, that is, when no actual pay was involved, is in the romantic novel Doctor Sandy, 1965, by the British author Margaret Malcolm:
This isn’t like an ordinary marriage sweetie. With royal families involved, it’s as much a treaty as anything else. The politics are above my pay grade, but even I know everything could fall apart in a blink.
The phrase didn’t begin to appear commonly in US newspapers until the 1970s and much later in other parts of the world.
In the UK, the related expression ‘working to rule’ was more common. That referred to a tactic used by trade unionists in disputes in the 1970s, who instructed their members only to undertake work for which they were explicitly contracted.
