Apparatus and an associated method for facilitating paging of an access terminal operable in a radio communication system. A paging message is formed that includes either partial identities of access terminals that are to be paged or paging indicators. Selection is made as to whether partial identities or paging indicators are to be used responsive to the number of partial identities that have common portions. If a large number of partial identities have common portions, the paging message is formed of partial identities. Otherwise, the paging message is formed of paging indicators.