We've never done this without computers so for a good part of the process the most i can do is imagine what a paper based one would look like.
The Order would probably look pretty much like an invoice. The order lines would be displayed in a table like structure with the following columns: Line Number, SKU, Product Name, Quantity, Price. The line number would just be an ordinal number (starting from 1) and not an ID. The order would be given to a Shipper (warehouse employee) to start processing. The Shipper creates a Pick List by extracting the essential information from the Order (SKU and quantity) and asks a Runner (another warehouse employee) to locate and fetch them (obviously this operation is more efficiently done in bulk which is what happens in reality). The Runner locates the items based on a mapping list (SKU to warehouse location), picks up the items from the shelves and returns them to the Shipper. The Shipper decides if the returned items can be packed together in a single shipment or if they need to be part of multiple shipments. Assuming he needs multiple shipments, he chooses appropriate boxes for them and starts packing. As soon as a package is complete, he creates a document listing the items in that package. Say he calls that document a Shipment and it contains the order number it was built for and a grid with the following columns: Line Number, SKU, Quantity. No information about the order line is present in this document. The fact that the same product is present in multiple order lines is irrelevant to him (he effectively sums them grouped by SKU). He also weighs the package and fills in the dimensions and weight on the Shipment document. He creates another document (called a Shipping Slip) that contains the shipping and the return addresses and glues it to the package. After he finishes packing all the packages for that order, he calls the Courier to come pick them up and places the order into the "to be picked up" pile. The Runner then takes the package to a warehouse location designated for pick up.
It may happen that after the packages are complete and placed in the pick up location, the store faxes us an updated version of the order that is to replace the old one. Say this new order contains fewer items and some order lines that were present in the previous order are missing in this new one. The Shipper looks over the existing Shipment documents and compares their content with the items in the new Order. If some of the packages need to be returned to stock or rebuilt (just a few items removed) he marks the Shipment document of those packages as cancelled, and asks the Runner to return the items in the packages to stock. He then proceeds to create new packages and Shipment documents for them following the same process that was previously described.
It's pretty obvious that as far as this process is concerned, the Shipper does not need to know the IDs or line numbers of order lines. He does however maintain those counters i was talking about in his mind while packaging. If the number of packages is big he might use some paper based external memory either by scribbling on the order document itself or on some disposable piece of paper.
The problem comes after the packages are shipped and is caused by the requirements of the store the order came from. The Shipper needs to notify the store with the packages he created, including the order lines numbers and the quantity present in that shipment from each order line. Presumably the store would use this information to compute how many items and from which order lines are still to be shipped (in case the order was only partially fulfilled). No non-computer based stores would ask for this of course, but alas, platforms like Shopify do! In order to accommodate this, during the packaging process the Shipper would most probably need to maintain a new column Order Line Number in his Shipment document. This way, when the notification time comes he would be able to just fax the Shipment documents and it would all be done.