Methods, non-transitory computer readable media, and computing devices are disclosed that facilitate efficient storage operations using variable length encoded segment maps for deduplicated objects. A key name and elements of a segment list are received with a request to store an object. Each of the elements corresponds to a segment associated with the object and comprises a segment hash. A segment map is generated for the object. The segment map includes a header and entries. Each of the entries includes at least an expanded offset, one of the segment hashes, and a start offset. The segment map is stored in an object store, as associated with the key name, along with segment data included in at least one of the elements.