The "hike" in T4 that everyone complains about is not that long (by world standards anyway). From furthest gate in T4 to luggage hall is about 400m. By comparison from the far gates in T2 (new pier) to immigration is 480m. In T1, furthest gate to luggage hall is about 300m. (For reference, Brisbane Intl has a similar walk from the far gates to immigration of 400m. And SYD T2 can have 300m walks, so not all that different).
If you want to whinge about airport walks, have used BRU a couple of times (which has similar pax numbers to MEL), on Brussels Airlines (SN) lying a non-Schengen flight. The only lounge non-home carrier star golds can access in the Schengen zone, and as a result I've had a couple of 1km walks from lounge to gate, with a stop at immigration enroute.