A mass storage system employs a paging table for memory page redirection and maintains the paging table for power loss recovery (PLR) using a FIFO queue of paging table (L2P) segments to be written to non-volatile memory. The FIFO queue identifies a sequence of the L2P segments in conjunction with sequence number and marking data of the affected segments for recreating the paging table. Upon power failure, a power loss recovery (PLR) mechanism scans for the last segment written based on the FIFO queue. The PLR process recovers unwritten paging table entries by replaying the corresponding changes in the order defined by the sequence numbers. The recovery process continues for each sequence number in the current context, until the L2P information in the paging table is recreated to the point just prior to power loss.