I don't think fragmentation is the issue.
The OS doesn't search the page tables. The __CPU__ does, EVERY single time any program does a memory lookup (load/store operation), the CPU may have to traverse the page table. Page-table entries are often cached in the TLB-cache, but if the cache is full, a full table-traversal is necessary.
Its clear that page-tables are optimized for minimum latency: so that the smallest area of the CPU can be used, and the simplest hardware can implement the page-lookup procedure.
"blah = blah->next" is a very common pattern in programming. Since the page-table implementation in the CPU can speed this operation up (or slow it down), its extremely important to optimize for absolute fastest latency.
-----
A lot of stuff goes on with "blah = blah->next". If blah->next is outside the TLB cache, the CPU will have to jump to the page-table, traverse the 1st, 2nd, and 3rd levels of paging (looking for the physical location of blah->next).
A "variable length page" would complicate this lookup severely: the CPU wouldn't know which offset to lookup pages, and your non-TLB pages will be much much slower as a result.
x86 "huge pages" are based on only searching one (1GB) or two (2MB) layers of the page-lookup procedure, instead of all three (going down to 4kB pages). That's how you get support for other sizes without variable-length entries in the page tables / page directory table / etc. etc.