Turns out this is a non-issue. I wasn't running the same commands on the shell vs the rest API like I thought.
On the rest API, I was giving two filters, a page filter and a prefix filter.
On the HBase shell I was running
scan 'beacon', {STARTROW => 'ff', FILTER => "PageFilter(25)"}
The STARTROW isn't the same as a prefix filter. It is actually doing something more like setting a full beginning row key, and thus make the scan performant as it's not traversing the whole table.
Turns out, this is what I should have been doing in the rest API call too. When I set a start and end row in addition to a prefix filter and page filter, it works quickly and as expected.
https://community.hortonworks.com/articles/55204/recommended-way-to-do-hbase-prefix-scan-through-hb.html
Should I use prefixfilter or rowkey range scan in HBase