Graphene-based paper materials attract particular interests recently owing to their outstanding properties, the key of which is their layer-by-layer hierarchical structures similar to many biological materials such as bone, teeth and nacre, combining intralayer strong sp2 bonds and interlayer crosslinks for efficient load transfer. Here we firstly study the mechanical properties of various interlayer and intralayer crosslinks through first-principles calculations, and then perform continuum model analysis for the overall mechanical properties of graphene-based paper materials. We find that there is a characteristic length scale l0, defined as , where D is the stiffness of the graphene sheet, h0 and G are height of interlayer crosslink and shear modulus respectively. When the size of the graphene sheets exceeds 3l0, the tension–shear (TS) chain model, which is widely used for nanocomposites, fails to predict the overall mechanical properties of the graphene-based papers. Instead we proposed here a deformable tension–shear (DTS) model by considering elastic deformation of graphene sheets, also the interlayer and intralayer crosslinks. The DTS is then applied to predict the mechanical properties of graphene papers under tensile loading. According to the results we thus obtain, optimal design strategies are proposed for graphene papers with ultrahigh stiffness, strength and toughness.